[컴퓨터알고리즘] 2장 - 합병 정렬

재귀적 알고리즘

분할 정복의 핵심 아이디어

- 큰 문제를 작은 문제들로 분할한다. (상수 비율로) 상수나 변수로 

- 각 작은 문제들을 재귀적으로/명시적으로 푼다

- 작은 문제들을 결합하여 처음 문제를 푼다.

 

Merge Sort 합병정렬

MERGE-SORT A[1..n]
    1. If n=1, done
    2 .Recursively sort A[1.. ⌈n/2⌉] and A[⌈n/2⌉+1..n]

    3. Merge the 2 sorted lists

Key Subroutine: MERGE (결합 단계)

 

Merge 합병정렬 수도 코드

MERGE(A,p,q,r)
    n1 = q - p + 1 # 왼쪽 부분리스트 원소의 개수
    n2 = r - q # 오른쪽 부분리스트 원소의 개수
    let L[1..n1+1] and R[1..n2+1] be new arrays
    for i = 1 to n1
    	L[i] = A[p+i-1]
    for j = 1 to n2
    	R[j] = A[q+j]
    L[n1+1] = 무한대
    R[n2+1] = 무한대
    i = 1
    j = 1
    for k = p to r
    	if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1

A: 정렬할 배열, p: 배열의 시작 인덱스, q: 배열의 중앙 인덱스 (p+r)/2 (낮은 중앙값), r: 배열의 끝 인덱스

n1은 배열 앞에서부터 1/2 원소의 갯수, (q번이 홀수인 경우 이 쪽에 포함), n1은 배열 나머지 1/2의 원소 갯수이다.

배열 L과 R을 만든다.

L에 A의 원소들을 A[p+i-1] 넣는다.

R에 A의 원소들을 A[q+j]로 넣는다.

// 각각 n1+1과 n2+1번 원소는 경계값 용도로, 알고리즘을 더 쉽게 수행하기 위해 무한대(큰 값)을 넣었다.

i=1, j=1 초기화한다.

k=p부터 r까지, L[i]와 R[j] 중 더 작은 값을 A[k]에 넣는다. 넣고 나면 L또는 R의 인덱스를 증가시킨다.

A[p..q], A[q+1..r]

 

두 정렬된 배열을 합치는 부분에서 루프 불변성을 보자

1. 초기조건: 참. k=p, A[p..k-1]이 비어있다.

2. 유지조건: 루프 불변성을 만족시킴을 보이기 위해 L[i]>R[j]로 가정한다.

3. 종료조건: k=r+1. 루프 불변성에 의해 A[p..k-1], 즉 A[p..r]은 r-p+1 개의 (L과 R에서 온) 요소들을 오름차순 정렬된 순서로 갖는다.

 

n개의 요소들을 합치는 데에는 Θ(n)의 시간이 걸린다. (선형)

 

어떻게 재귀적 알고리즘이 옳음을 보일까?

귀납법으로: base case, inductive hypothesis, step

 

Merge Sort의 분석:

T(n) = Θ(1) // n=1일 때

       + 2T(n/2) // 재귀적으로 절반씩 나누어 정렬하는 부분

       + Θ(n) // merge가 n번 일어남

 

Merge Sort의 재귀 호출

T(n) = { Θ(1) if n=1;

            2T(n/2) + Θ(n) if n>1;

트리를 그려보면 각 레벨별로 cost = cn. | h = lgn. (h=0(1레벨)에서도 cost가 든다.) | 총 비용은 cn(lgn + 1) = cn(lg n) + cn

 => Θ(nlgn)

 

MERGE 합병정렬 C언어 코드

// C언어
#include <stdio.h>
#include <stdlib.h>

void Merge(int A[], int p, int q, int r) {
    int i, j, k;
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int *)malloc(sizeof(int)*n1);
    int *R = (int *)malloc(sizeof(int)*n2);
    
    for (i=0; i < n1; i++) {
        L[i] = A[p + i];
    }
    for (j=0; j < n2; j++) {
        R[j] = A[q + 1 + j];
    }
    i = 0;
    j = 0;
    k = p;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            A[k++] = L[i++];
        } else {
        	A[k++] = R[j++];
        }
    }
    while (i < n1) {
        A[k++] = L[i++];
    }
    while (j < n2) {
        A[k++] = R[j++];
    }
    free(L);
    free(R);
}

void MergeSort(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

int main()
{
    int A[] = {3, 2, 5, 3, 6, 5, 3, 1, 2, 7};
    MergeSort(A, 0, 9);
    for (int i = 0; i < 10; i++)
        printf("%d ", A[i]);
    return 0;
}