[C언어 알고리즘] 정렬 (8) - 병합정렬 (Merge Sort)

병합정렬은 이미 정렬된 두 파일을 병합(Merge)하는 방식을 일반화한 것입니다. 병합정렬은 아주 자연스럽고 이해가 쉽고 빠른 속도를 가지는 정렬방식입니다.

병합정렬은 두 자료를 순차적으로 읽어가면서 비교 접근하는 방법으로 연결리스트(Linked-list), 테이프(Tape)같은 순차적 접근만이 용이한 자료구조나 기억장치에서 유용하고 유일한 정렬방법입니다. 병합정렬은 메모리내부(internal)정렬뿐 아니라 외부(external) 정렬에서도 사용합니다.

이번 포스팅에서는 하나의 배열을 최소 단위 (배열의 1개요소)부터 단위를 2배로 늘려가며 정렬하는 예제에 대해 공부합니다.

우선 병합정렬의 기본 의사코드(Pseudo code)를 보도록 하죠.

1. size = 1
2. size가 N보다 작을 동안
   2.1. size의 크기로 배열을 분할하여 두세트씩 차례로 병합한다.
   2.2. size를 두배하여 다시 수행한다.

우선 최소단위인 size를 1로 하여 데이터의 최소크기의 인접한 두개를 한세트로 비교하여 병합을 수행합니다. 그다음 size를 2배로늘려 병합을 반복하고, 4배로, 8배로 .... size가 데이터 전체의 크기보다 작은 동안은 병합을 반복합니다. 병합에 대한내용은 아래 코드와 같습니다.

병합하기
1. i = j = k = 0;
2. while (i < na || j < nb)
   2.1 a[i] <= b[j] 이고 i < na이면 c[k++] = a[i++]
   2.2 a[i] <= b[j] 이고 i >=na 이면 c[k++] = b[j++]
   2.3 a[i] > b[j] 이고 j < nb이면 c[k++] = b[j++]
   2.4 a[i] <= b[j] 이고 j >=nb 이면 c[k++] = a[i++]

두 배열을 a와 b라고 했을 때, 두배열의 끝에 도달하기 전까지 반복을 합니다. 반복내용은 두 배열에서 값을 순차적으로 읽어 작은 값인 경우 새로운 배열 c에 추가하는 작업입니다.

size가 1일때인 첫번째 단계의 수행 전후는 아래와 같습니다. 병합은 'l'과 'e', 'a'와 'r', 'n'과 'a' ... 'h'와 'm'까지 최소단위인 크기가 1인 배열에서 값을 비교하여 정렬을 합니다.

size 1일때 정렬

size가 2일때 병합은 'e, l'과 'a, r', 'a, n'과 'g, l', ...등 크기가 2인 배열 두개간 값을 비교하여 정렬을 합니다.

size 2일때 정렬

size가 4일때 병합은 'a, e, l, r'과 'a, g, l, n' ....등 크기가 4인 배열 두개의 값을 순차적으로 비교하여 정렬을 합니다.

size 4일때 정렬

마지막은 남은 두 배열을 마찬가지 방법으로 정렬을 하면 됩니다. 참 쉽네요.

C로 구현한 소스코드는 아래와 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print_data(char a[], int n);

void merge_sort(char a[], int n)
{
    int i, j, k, first, second, size;
    char *b;
    b = (char *)malloc(sizeof(char)*n);	/* 병합할 새로운 작업 공간 할당 */
    
    for (size = 1; size < n; size *= 2) {
        first = -2*size;
        second = first + size;
        while (second + size*2 < n) {	/* 두번째 배열의 인덱스가 n보다 작은 동안 */
            first = second + size;
            second = first + size;
            i = first;
            j = second;
            k = first;
            while (i < first + size || (j < second+size && j < n)) {	/* 실제 병합하는 코드*/
                if (a[i] <= a[j]) {
                    if (i < first+size) {
                        b[k++] = a[i++];
                    } else {
                        b[k++] = a[j++];
                    }
                } else {
                    if (j < second+size && j < n) {
                        b[k++] = a[j++];
                    } else {
                        b[k++] = a[i++];
                    }
                }
                
            }
            
        }
        for (i = 0; i < n; i++)
            a[i] = b[i];
        print_data(b, n);
    }
    
    free (b);
}

void print_data(char a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf ("%c ", a[i]);
    }
    printf ("\n");
}

void main (int argc, char *argv[])
{
    char data[] = "learnalgorithm";
    print_data(data, strlen(data));
    merge_sort(data, strlen(data));
}

다음은 실행결과입니다.

PS C:\CS> .\merge_sort.exe
l e a r n a l g o r i t h m
e l a r a n g l o r i t h m
a e l r a g l n i o r t h m
a a e g l l n r h i m o r t
a a e g h i l l m n o r r t

병합정렬은 내용은 굉장히 쉽습니다만, 구현한 내용이 그리 쉽지많은 않습니다. 코드를 잘 보고 디버깅 코드를 여기 저기 넣어보면서 이해하면 조금 더 도움이 될듯 합니다. 

지금까지 병합정렬(Merge sort)이었습니다. 빠이~