합병 정렬 (Merge Sorting)

비효율적이지만 간단한 정렬 방법들은 입력 데이터가 많지 않을 때는 사용하기에 부담이 적다.

하지만 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있다면 이 방법들은 적절하지 못하다.

합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

합병 정렬은 분할 정복(divide and conquer)방법에 바탕을 둔다.

분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

분리된 문제가 아직도 해결하기 어렵다면(충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용한다.

분할 정복 방법은 대개 순환 호출을 이용하여 구현된다.

합병 정렬은 다음 단계들로 이루어진다.

1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할

2. 정복(Conquer) : 부분 배열을 정렬. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용.

3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병

예를 들어 요소의 갯수가 8개이고

27 10 12 20 25 13 15 22 라고 한다면

1. 분할(Divide) : 배열을 (27 10 12 20), (25 13 15 22)의 2개 부분 배열로 나눈다.

2. 정복(Conquer) : 부분 배열을 정렬하여 (10 12 20 27)과 (13 15 22 25)를 얻는다.

3. 결합(Combine) : 부분 배열을 통합하여 (10 12 13 15 20 22 25 27)을 얻는다.

각각의 부분 배열들을 정렬할 때도 합병 정렬을 순환적으로 적용하면 된다.

위의 예에서 부분 배열인 (27 10 12 20)을 정렬 할 때도 합병 정렬의 개념을 적용한다.

순환적으로 호출하기 때문이다.

 

합병 정렬의 알고리즘은 다음과 같다.

1. 나누어진 구간의 크기가 1 이상이면

2. 중간 위치를 계산한다.

3. 앞쪽 부분 배열을 정렬하기 위해 merge_sort함수를 순환 호출

4. 뒤쪽 부분 배열을 정렬하기 위해 merge_sort함수를 순환 호출

5. 정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열로 만든다.

합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

합병 자체는 어렵지 않지만 추가적인 리스트가 필요하다.

합병 알고리즘은 2개의 리스트의 요소들을 맨 앞부터 하나씩 비교하여 두 개의 리스트 요소 중 더 작은 요소를 새로운 리스트로 옮긴다.

둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.

만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사한다.

전체 프로그램

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

#define MAX_SIZE 10

int sorted[MAX_SIZE]; // 추가 공간 필요

// i는 정렬된 왼쪽 리스트에 대한 인덱스
// j는 정렬된 오른쪽 리스트에 대한 인덱스
// k는 정렬될 리스트에 대한 인덱스
void merge(int list[], int left, int mid, int right) {
    int i, j, k, l;
    i = k = left;
    j = mid + 1;
    
    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right) {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
    
    // 남아 있는 레코드의 일괄 복사
    if (i > mid)
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    else
        for (l = i; l <= mid; l++)
            sorted[k++] = list[l];
    
    // 배열 sorted의 리스트를 배열 list로 재복사
    for (l = left; l <= right; l++)
    list[l] = sorted[l];

}

void merge_sort(int list[], int left, int right) {
    int mid;
    if (left < right) {
        mid = (left + right) / 2; // 리스트의 균등 분할
        merge_sort(list, left, mid);    // 부분 리스트 정렬
        merge_sort(list, mid+1, right); // 부분 리스트 정렬
        merge(list, left, mid, right); // 합병
    }
}

void main() {
    int list[MAX_SIZE];
    
    printf("<합병 정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < MAX_SIZE; i++) {
        list[i] = rand() % MAX_SIZE;
        printf("%d ", list[i]);
    }
    printf("\n");
    
    merge_sort(list, 0, MAX_SIZE-1); // 합병 정렬 호출
    
    printf("최종 정렬 결과 : ");
    for (int i = 0; i < MAX_SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");
    system("pause");

}

 

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

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

#define MAX_SIZE 40000

int sorted[MAX_SIZE]; // 추가 공간 필요

// i는 정렬된 왼쪽 리스트에 대한 인덱스
// j는 정렬된 오른쪽 리스트에 대한 인덱스
// k는 정렬될 리스트에 대한 인덱스
void merge(int list[], int left, int mid, int right) {
    int i, j, k, l;
    i = k = left;
    j = mid + 1;
    
    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right) {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
    
    // 남아 있는 레코드의 일괄 복사
    if (i > mid)
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    else
        for (l = i; l <= mid; l++)
            sorted[k++] = list[l];
    
    // 배열 sorted의 리스트를 배열 list로 재복사
    for (l = left; l <= right; l++)
        list[l] = sorted[l];

}

void merge_sort(int list[], int left, int right) {
    int mid;
    if (left < right) {
        mid = (left + right) / 2; // 리스트의 균등 분할
        merge_sort(list, left, mid);    // 부분 리스트 정렬
        merge_sort(list, mid + 1, right); // 부분 리스트 정렬
        merge(list, left, mid, right); // 합병
    }
}

void main() {
    int list[MAX_SIZE];
    
    for (int i = 0; i < MAX_SIZE; i++)
        list[i] = rand() % MAX_SIZE;
    
    clock_t start = clock(); // 시간재기 시작
    merge_sort(list, 0, MAX_SIZE - 1); // 합병 정렬 호출
    clock_t end = clock(); // 시간재기 끝
    
    double diff = (double)(end - start) / 1000;
    printf("합병 정렬\n크기 : 40000개\n%.4lf초\n", diff);
    system("pause");

}

 

합병 정렬은 순환 호출 구조이다. 따라서 레코드의 개수 n이 2의 거듭제곱이라고 가정하고 순환의 호출의 깊이가 얼마나 되는지를 알아볼 필요가 있다.

​

만약 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.

따라서 일반적으로 이라고 하면 부분 배열의 크기는 이 되어 순환 호출의 깊이는 k가 될 것이다.

여기서 ​이다.

​

배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산은 수행되지 않는다.

부분 배열이 합쳐지는 merge 함수에서 비교 연산과 이동 연산이 수행된다.

즉, 순환 호출의 깊이 k만큼 합병 단계가 필요하다.

​

<비교 연산>

인 경우를 보면 크기 1인 부분 배열 2개를 합병하는 데는 최대 2개의 비교 연산이 필요하고, 부분 배열 쌍이 2쌍이 있으므로 역시 4*2 = 8번의 연산이 필요하다.

마지막 합병 단계인 크기가 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하다. 따라서 또한 8*1번의 연산이 필요하다.

일반적인 경우를 유추해보면 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요하다. 그러한 합병 단계가 ​번 만큼 있으므로 총 비교연산은 최대 ​번 필요하다.

<이동 연산>

하나의 합변 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 하므로 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다. 총 ​개의 합병 단계가 필요하므로 총 ​개의 이동 연산이 필요하다.

결론적으로 합병 정렬은 비교/이동 연산의 경우 ​의 복잡도를 가지는 알고리즘이다.

합병 정렬의 다른 장점은 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받는 것이다.

즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.

최악, 평균, 최선의 경우가 다 같이 ​인 정렬방법이다.

단점으로는 임시 배열이 필요하고, 레코드들의 크기가 큰 경우에는 이동횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

그러나 만약 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 다른 어떤 정렬 방법(퀵 정렬 포함)보다 효율적일 수 있다.