4. 병합 정렬(Merge Sort)

Goal

---

• Merge Sort란?
• Merge Sort 구현
• Merge Sort 시간복잡도, 공간복잡도 계산

 

Merge Sort란?

---

Merge Sort는 분할 정복(Divide and Conquer) 방법 중 하나의 방법으로, 주어진 문제를 작은 문제로 분할하고 각 문제를 해결한 다음, 결과를 모아서 문제를 해결하는 방식이다. 평균적으로 매우 빠른 수행 속도를 보여주는 정렬 방법이고 안정 정렬에 속하나, 정렬해야하는 데이터만큼 메모리를 추가적으로 더 사용한다는 점이 단점이다.

과정은 아래와 같다.

1. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눈다.
2. 리스트의 길이가 0 혹은 1이라면 이미 정렬된 것으로 보고, 그렇지 않으면 계속 절반으로 나눈다.
3. 각 부분의 리스트를 합병 정렬을 통해 재귀적으로 정렬시킨다.
4. 합병 정렬이 끝나면 정렬된 리스트가 남는다.

 

Merge Sort 구현

---

Divide and Conquer 방식을 구현하는 것은 재귀적으로 구현하는 것이 핵심으로, 요소를 쪼갠 후 다시 합병시키는 과정을 재귀적으로 구현한다. 때문에 왼쪽을 분할, 오른쪽을 분할 후 병합하는 과정을 재귀적으로 구현한다.

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

#define MAX_SIZE 10000
int sorted_list[MAX_SIZE];

int mknum() {
    int random = (rand() % 100) + 1;

    return random;
}

void marge(int list[], int left, int mid, int right) {
    // i: index of left end
    // j: index of right end
    // k: index of sorted list
    /* process of merging left and right */
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    while(i <= mid && j <= right) {
        if(list[i] <= list[j]) {
            sorted_list[k++] = list[i++];
        } else {
            sorted_list[k++] = list[j++];
        }
    }

    if(i > mid) {
        for(l=j; l<=right; l++) {
            sorted_list[k++] = list[l];
        }
    } else {
        for(l=i; l<=mid; l++) {
            sorted_list[k++] = list[l];
        }
    }

    for(l=left; l<=right; l++) {
        list[l] = sorted_list[l];
    }
}

void marge_sort(int list[], int left, int right) {
    if(left < right) {
        int mid = (left + right) / 2;

        marge_sort(list, left, mid);
        marge_sort(list, mid + 1, right);
        marge(list, left, mid, right);
    }
}

int main() {
    int i;
    int n = MAX_SIZE;
    int list[n];

    printf("Unsorted list :");
    for(i=0; i<n; i++) { //make random list
        list[i] = mknum();
        printf(" %d", list[i]);
    }
    printf("\n");

    //timer
    clock_t start, end;

    start = clock();

    marge_sort(list, 0, n-1);

    end = clock();

    printf("Sorted list :");
    for(i=0; i<n; i++) { //print sorted output
        printf(" %d", list[i]);
    }
    printf("\n");

    //run-time result
    printf("Run time : %f\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

 

시간복잡도

---

병합 정렬은 분할 정복을 통해 구현된다는 것을 유념하고 계산한다.

 

비교 횟수 먼저 계산한다.

 

분할 과정에서는 비교, 이동이 수행되지 않는다. 크기에 절반씩 잘라내기만 하므로, 따로 계산이 이루어지지 않는다.

 

합병 과정에서는 크게 2가지를 생각해 볼 수 있는데, 합병 단계의 횟수, 각 합병 단계의 연산 횟수를 생각해 볼 것이다.

  데이터의 갯수 n이 2의 거듭제곱(2^k)이라고 가정해보자. 만약 데이터의 갯수가 2^5개라면, 첫 합병과정에서 2^4개, 두 번째 합병 과정에서 2^3개, 세 번째 합병 과정에서 2^2개 ... 마지막 다섯 번째 합병 과정에서 2^0개로 합병이 끝난다. 이를 통해 합병 단계의 갯수는 거듭제곱의 횟수, 즉 k = log₂n임을 알 수 있다.

  위의 2^5짜리 데이터를 다시 생각해보자. 1개짜리 배열 2개를 합하는 데는 최대 2번의 연산이 필요하다(첫 번째 데이터 한번, 두 번째 데이터 한번). 또한, 이 과정이 필요한 쌍이 16개이므로, 첫 합병에는 2 * 16 = 32회 시행된다. 두 번째 합병에는 2개짜리 배열 2개를 합하는 데는 최대 4번의 비교 연산이 필요하고, 이 과정이 필요한 쌍은 8개이므로, 4 * 8 = 32회 시행된다. 이를 일반화하면, 한 합병 단계에서는 데이터의 크기 n만큼 비교 연산을 하는 것을 알 수 있다.

종합하면, 합병 과정에는 (합병 단계의 수) * (각 합병 단계의 비교 연산) = nlog₂n만큼의 연산이 시행된다.

 

이동 횟수의 계산 또한 비교횟수 계산과 똑같이 이루어진다. 단, 각 합병 단계에서 이동 연산을 할 때 횟수가 조금 달라지는데, 임시 배열에 복사했다가 다시 가져와야하므로 이동 횟수는 연산 횟수의 2배다. 때문에 합병 과정에는 (합병 단계의 수) * (각 합병 단계의 비교 연산) = 2nlog₂n만큼의 연산이 시행된다.

 

이를 종합하면, 시간복잡도는 nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)

 

공간복잡도

---

병합정렬은 병합할 데이터의 크기만큼 다른 배열이 필요하다. 때문에 복잡도는 최선, 평균, 최악 모두 2n을 가진다.

 

장점

---

• 안정정렬, 데이터 분포에 영향을 덜 받는다. 이말인즉, 입력 데이터가 무엇이던 정렬에 걸리는 시간은 똑같다.
• 만약 데이터가 연결 리스트(Linked List)라면, 정렬과정에서 데이터를 가리기는 주소만 변경되므로 데이터 이동은 매우 작아진다. 이를 활용하여 제자리 정렬로도 구현 가능하다.

 

단점

---

• 데이터가 배열(Array)라면, 데이터 만큼의 임시 배열이 필요하다. 이는 제자리 정렬이 아니라는 의미로, 데이터의 크기가 크면 클수록 이동 횟수가 많아진다는 뜻이다. 따라서 많은 시간이 낭비되게 된다.