해당 글은 시험 대비로 급하게 필기한 내용이다.
다음에 기회가 된다면 더 좋은 퀄리티의 글로 바꾸어 나갈 예정이다.
교재가 원서여서
키워드들은 대부분 영단어로 작성할 예정이다.
교재는 Richard E. Neapolitan의 Foundations of Algorithms이다.
Merge Sort
이제부터는 본격적으로 Divide-and-Conquer 방식을 이용한 정렬을 소개한다.
이름으로부터 알 수 있듯,
여러 개로 리스트를 쪼갠 후,
이들을 병합하는 과정에서 정렬이 이루어지는 것이다.
우리는 리스트를 계속 쪼개다 보면
결국 원소들이 낱낱으로 리스트가 된다는 사실을 알 수 있다.
예를 들면, S가 {1, 3, 5, 7, 9}일 때
가장 많이 S를 분할하면(Divide)
{1}, {3}, {5}, {7}, {9}가 된다.
그런데, 원소가 애당초 하나밖에 없으므로
이미 이들은 정렬되었다는 논리이다.
그리고 인접한 리스트 쌍을 합쳐본다:
{1, 3}, {5, 7}, {9}
{1, 3} {5, 7, 9}
{1, 3, 5, 7, 9} (완료)
만약, 이 과정에서 인접한 sublsit를
모두 정렬하면서 (Conquer) 합치게 되면 (Combine)
마지막에 도출되는 list는 그 규칙을 그대로 이어받아서
정렬된 최종 list를 반환하게 된다.
(물론, 이 예시에서는 list가 모두 정렬이 되어 있다.
왜냐하면 지금은 합병을 위주로 설명하고 싶기 때문이다.)
대충 정렬이 된다는 것은 이해가 되겠지만,
그 구체적인 방법에 대한 논의를 더 할 필요가 있어 보인다.
다시 {1, 3}, {5, 7}, {9}로 돌아오자.
이 부분에서 이미 문제가 있는데,
{1, 3}과 {5, 7}를 합쳐야 할지
{5, 7}과 {9}를 합쳐야 할지 애매하다는 것이다.
이를 해소하기 위해서는
분할 방식의 역순으로 하는 것이 가장 현명하다.
그리고, 이 과정에서 재귀 호출을 이용하여야 한다.
왜냐하면, 함수의 호출이 끝나면
return의 순서는 역순으로 시작되기 때문이다.
즉, 위 그림과 같은 분할 규칙을 이용하면
{1} {3} {5} {7} {9}
{1, 3} {5} {7, 9}
{1, 3, 5} {7, 9}
{1, 3, 5, 7, 9} 순으로 합쳐지는 것이다.
이제부터는 두 sublist를 정렬하는 방식에 대해 알아보자.
합병 정렬의 최대 장점은
이미 정렬된 두 리스트를 정렬하는 것에 있다.
일단, 오름차순으로 정렬된 A와 B를 합병해보자.
일단, A[1..m], B[1..p]를 입력받았다고 해보자.
일단, 정렬한 원소를 입력할 list가 따로 필요하므로
list C[1..m+p]를 생성한다.
이제부터 list에 원소를 담아본다.
i = j = 1부터
A[i]와 B[j]를 비교하고
A[i]가 B[j]보다 크면
B[j]를 C[1]에 담는다.
그러면 A[i]는 C[2]에 넣으면 될까?
A[i]가 B[j+1]보다도 크면
A[i]를 C[2]에 담았을 때 문제가 된다.
물론, B[j]보다 B[j+1]이 항상 크므로
B[j]를 C[1]에 담는 것은 문제가 되지 않는다.
A와 B 사이에는
정렬 관계가 없다는 것을 잊으면 안 된다.
이 내용을 일반화해보면
i=j=k=1로 대입한 뒤,
A[i] > B[j]를 만족하면
A[i]를 C[k]에 담고 k=k+1로 갱신한다.
(C에는 계속해서 원소를 담아야 하므로)
그 다음에는
j=j+1에 대해 A[i] > B[j]를 비교한다.
(부등식을 보존하는 형태로 고려한다.)
A[i] <= B[j] (else)인 경우, 마찬가지로 C에 담고
i=i+1에 대해 A[i] > B[j]를 비교한다.
그럼 이 loop의 탈출 조건을 조사해보자.
i 또는 j는 계속해서 증가하게 된다.
따라서, 여기서는 무조건 상한을 생각해야 한다.
(Segment Fault 등의 문제가 생길 수 있다.)
따라서, i>m 또는 j>p일 때, loop를 탈출하게 된다.
그럼, 결국엔 A와 B 중
원소가 C에 다 담기지 않은 list가 존재할 텐데
나머지 원소들은 어차피 C에 담긴
모든 원소들보다 큰 값이므로
그저, 남은 list의 원소를 모두 C에 순서대로 담기만 하면 된다.
i>m인 경우, 남은 j에 대해 B[j]를 모두 C[k]에 담으면 되며,
j>p인 경우, 남은 i에 대해 A[i]를 모두 C[k]에 담으면 된다.
Time Complexity Analysis
이제부터 의사코드를 구현해보겠다.
일단, 앞서 말한 내용을 가볍게 정리해보자.
Divide: 원소 개수가 1이 될 때까지 list를 분할한다.
Conquer: 원소 개수가 1이 되면 return하고, 인근의 sublist를 합쳐서 정렬한다.
Combine: 정렬된 sublist를 모두 합쳐서 정렬된 list를 만든다.
일단, 합병 정렬은 재귀 호출을 통해 진행되므로
모든 연산 횟수는 같은 depth의 함수에 대해 진행하여야 한다.
그런데 같은 depth에 있을 수 있는 원소들의 총 개수는
list S의 사이즈인 n이라고 생각해볼 수 있다.
가령, 아까 보여줬던 그림에서
두 번째 분할까지 모든 sublist의 원소 개수를 합치면
원래 list size인 5임을 알 수 있다.
그럼, 초기 list 개수가 $2^n$이면
결국 모든 sublist가 같은 depth에서 모두 분할되므로
이때는 모든 sublist에 대해
같은 depth에서 return이 일어난다는 것을 알아야 한다.
즉, 한 depth에서 각각의 원소를 비교하여 합병하므로
그 depth에 속하는 원소의 최대 개수인 n를 비교한다는 것은
그 depth에서의 최악 시간 복잡도를 말하는 것과 같다.
그러면, 결국 depth가 m이면
최악 연산횟수는 대략 mn이 되므로
depth가 최악 시간 복잡도에 비례하며
depth를 줄여나간다는 것은
최악 시간 복잡도를 줄여나갈 수 있는 것이다.
그러나,
list를 10등분을 하던, 100등분을 하던
우리가 작성할 재귀만 무자비하게 늘어날 뿐이며
밑변환 공식을 잘 안다면
무슨 짓을 하더라도
$n\log_kn \in \Theta(\log_2 n)$이므로
결국엔 Time Complexity Analysis에서는 다 똑같다.
그래서, 이 글에서는 list를 이등분 하는 방식으로 진행하겠다.
merge_sort (int *S, int n) {
if(n > 1) { // n == 1에서 바로 return
// divide
int m = n / 2 // 절반을 기준으로 divide
int p = n - m
list U[1..m], V[1..p]
U[1..m] = S[1..m]
V[1..p] = S[m+1..n]
// 재귀를 통한 divide
merge_sort(U, m)
merge_sort(V, p)
// conquer, 모든 divide가 끝나고 실행됨
merge(U, V, m, p, S)
}
}
참고로, conquer 부분의 merge가 이해가 잘 안 될 수도 있는데,
merge가 실행되는 위치는 그 함수가 속한 depth이다.
즉, 아래에서 쭉 정렬해온 sublist 두 개를 받아서
(U, V로 나누었으니까,
역순으로 올라가면 다시 U와 V를 받을 것이다.)
그걸 merge하고 다시 위로 올리는 것이다.
따라서, 개별 함수에서 논리적인 오류는 없다.
이제는 따로 떼어놓은 interface인 merge를 구현해보자.
merge에 대해 다시 설명하자면
A[i]와 B[j]를 비교한 뒤
A[i]가 더 작으면, 일단 S[k]에 집어넣고
A[i]를 A[i+1]로 갱신한다.
그렇지 않으면, B[j]를 S[k]에 집어넣고
B[j]를 B[j+1]로 갱신한다.
그리고, A와 B중 남는 list가 있다면
S의 뒤에 모두 집어넣는다.
merge (int *U, int *V, int m, int p, int S) {
int i, j, k
while(i <= m and j <= p) { // i>m 또는 j>p에서 탈출
if(U[i] < V[j]) {
S[k] = U[i]
i++
}
else {
S[k] = V[j]
j++
}
k++ // k는 항상 갱신
}
// 탈출 후, 분기
if( i > m )
copy V[j..p] to S[k..m+p]
else copy U[i..m] to S[k..m+p]
}
일단, merge부터 시간 복잡도를 체크해보자.
비교연산만을 basic operation으로 삼아보면
while문을 가능한 많이 돌아야 연산 횟수가 늘어난다.
즉, 두 sublist의 size가 같고
A[i]와 B[i]의 인덱스의 값이 거의 비슷할 때
계속 A와 B가 교대로 S에 쌓이면서 Worst-case가 된다.
그럼, 결국엔 맨 마지막이 중요한데,
최종 결과물이
A - B - A - B - A - ... - A - B 순서로 쌓였다고 치자.
그럼, B에 대한 비교 연산은 필요할까?
이미 A가 모두 쌓였으므로
마지막 B의 원소가 S에 쌓일 때는
이미 loop문을 이탈하게 된다.
B - A - B - A ... - B - A 순이어도
매커니즘은 마찬가지이므로
연산 횟수는 항상
m+(p-1) 또는 (m-1)+p가 된다.
즉, merge에 대해 $W(m,\,p)=m+p-1$이다.
그럼, merge sort의 loop문을 통해
다시 최악 시간 복잡도를 확인해보면
$W(n) = W(m)+W(p)+(m+p-1)$임을 알 수 있다.
(말 그대로 loop의 순서 그대로다.
W(m), W(p)에서 merge_sort 재귀호출
m+p-1은 U와 V를 merge하는 것이다.)
일단, 처음 제공된 list의 size가 2의 거듭제곱이라 하면
$m = \cfrac{n}{2}$이고, $p = \cfrac{n}{2}$가 되므로
합병 정렬의 최악 시간 복잡도에 대해서는
$W(n)=2W\left(\cfrac{n}{2}\right)+n-1$이다.
또한, n = 1이면
merge_sort에서 바로 return되므로 $W(1) = 0$이다.
그렇다면, 점화식을 $\lg n$번 시행하면
$W(n)=2^{\lg n}W(1)+n\lg n - 1 - 2 - 4\cdots -\cfrac{n}{2}$
$=n\lg n-n+1 \in \Theta(n\lg n)$임을 알 수 있다.
근데, 일반적인 경우라 해도
$W(n)=W\left(\left\lfloor\cfrac{n}{2}\right\rfloor\right)+ W\left(\left\lfloor\cfrac{n}{2}\right\rfloor+1\right)+n-1$이므로
결국, 상수항이 바뀌지 않아서 최악 시간 복잡도는 같다.
이제부터는 이를 C언어로 구현해보겠다.
#include <studio.h>
#include <stdlib.h>
void merge(int *U, int *V, int m, int p, int *S) {
int i = 0, j = 0, k = 0;
while(i < m && j < p) {
if(U[i] > V[j]) {
S[k] = U[i];
i++;
}
else {
S[k] = V[j];
j++;
}
k++;
}
while(i < m) {
S[k++] = U[i++];
}
while(j < p) {
S[k++] = V[j++];
}
}
void merge_sort(int *S, int n) {
int m = n / 2;
int p = n - m;
if ( n > 1 ) {
// divide에서 sublist를 호출하지 않으므로
// S의 포인터를 기준으로만 분할한다.
merge_sort(S, m);
merge_sort(S + m, p);
// 포인터로만 divide 했으므로
// merge에서 원소를 담을 수 있도록 temp를 할당한다.
int *temp = (int *)malloc(n * sizeof(int));
merge(S, S + m, m, p, temp);
//temp[i]의 모든 원소를 다시 S에 씌운다.
for (int i = 0; i < n; i++) {
S[i] = temp[i];
}
free(temp);
}
}
이전 글에서 했던 세 정렬보다 확실히 코드가 복잡하다.
그러나, 비교 연산에 대한 최악 시간 복잡도로
$\Theta(n\lg n)$를 얻었다는 것에 의미를 두자.
list들을 만들었다는 것은
달리 말해 메모리 복잡도가 $O(n)$이라는 말과도 같으므로
메모리가 한정적인 경우에는 사용에 주의하자.
'컴퓨터 알고리즘 (학부)' 카테고리의 다른 글
| [알고리즘 필기] 2-2. 세 가지 정렬 (버블정렬, 삽입정렬, 선택정렬) (0) | 2025.04.18 |
|---|---|
| [알고리즘 필기] 2-1. 분할정복 알고리즘, 이진 검색 (1) | 2025.04.16 |
| [알고리즘 필기] 1. 알고리즘과 시간 복잡도 (0) | 2025.04.16 |