본문 바로가기

예전글 목록

[알고리즘] 합병 정렬 (The divide-and-conquer)


일명 합병 정렬은 merge sort로 잘 알려져 있으며 분할 정복 방식의 정렬 알고리즘이다.

divide: 주어진 문제를 작은 문제로 분할한다.
conquer: 작은 문제를 순환적으로 처리. 즉 더 작은 소문제의 순환이 없을때까지..
merge: 작은 문제에 대한 해를 합병하여 원래 문제에 해를 구한다.

다음 그림은 Introduction to Algorithms에 나와 있는 그림으로써 합병정렬의 모습을
보여 준다.


알고리즘의 Pseudu code는 다음과 같다.

MERGE(A, p, q, r)
n1 q - p + 1
n2 r - q
3  create arrays L[1 n1 + 1] and R[1 n2 + 1]
for i 1 to n1
5       do L[i] A[p + i - 1]
for j 1 to n2
7       do R[j] A[q + j]
L[n1 + 1]
R[n2 + 1]
10  i 1
11  j 1
12  for k p to r
13       do if L[i] R[j]
14             then A[k] L[i]
15                  i i + 1
16             else A[k] R[j]
17                  j j + 1



오늘 이를 바탕으로 오래간만에 프로그래밍을 해 보았다. 좀 엉성하기는 하지만 그래도 나름대로
잘 돌아가는 것 같다.