합병정렬 - 알고리즘

 

 Merge Sort

합병정렬은 mergesort(머지소트)라고도 불리우며 O(nlogn)의 복잡도를 가지는 정렬알고리즘이다. 합병정렬 또한 앞서 살펴본 분할정복법을 사용한다. 정렬은 해당 아이템의 수가 많은 수록 비교 및 삽입 연산이 많이 발생하게 된다. 따라서 그 연산을 최소화하기 위하여 정렬하고자 하는 해당 배열을 충분히 분할한 후 거꾸로 합병하면서 정렬을 하여 최종적으로 전체 배열의 정렬을 하는 방식이다.

합병정렬은 다음과 같은 절차로 진행된다.

1. 분할 : 배열을 n/2개 아이템으로 가진 2개의 부분배열로 분할한다.
2. 정복 : 정렬함으로써 각 부분배열을 정복한다(푼다). 배열이 충분히 작지 않으면 재귀 호출을 한다.
3. 통합 : 부분 배열에 대한 답들을 합병하여 하나의 정렬된 배열로 만든다.

배열을 2개 이상의 배열로 분할 할 수 있는데 n개의 배열로 분할하게 되면 n-원 합병정렬이 된다.

다음은 재귀적 방법을 이용하여 합병정렬을 구현한 것이다. 재귀적 함수에는 반드시 종료조건이 존재해야 한다. 종료조건은 배열의 크기가 1에 도달하는 경우가 되고, 바로 그 시점부터 합병이 시작된다.

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

#define KEY_SIZE   50    // 정렬할 배열의 크기

// 배열의 내용을 다른 배열로 복사하는 함수
void arrayCopy(const int src[], int dest[], int size)
{
      int i;
      for (i=0; i<size; i++) {
            dest[i] = src[i];
      }
}

// 분할된 부분배열을 합병하는 함수
void merge(int h, int m, int Ldiv[], int Rdiv[], int key[])
{
      int i, j, k;

      i = j = k = 0;
 
      while (i < h && j < m) {
            if (Ldiv[i] < Rdiv[j]) {
                  key[k] = Ldiv[i++];
            } else {
                  key[k] = Rdiv[j++];
            }
            k++;
      }
 
      /* 나눠진 두개의 배열에서 어느 한쪽이 더 큰경우
       * 나머지 배열의 요소를 복사한다.
       */
      if (i == h)
            arrayCopy(Rdiv+j, key+k, m-j);
      else
            arrayCopy(Ldiv+i, key+k, h-i);
}

// 합병정렬을 수행하는 함수
void mergeSort(int n, int key[])
{
      const int h = n/2;
      const int m = n -h;
      int L_index, R_index, key_index;
      int *Ldiv, *Rdiv;

      if (n>1) {
            Ldiv = (int *)malloc(h * sizeof(int));
            Rdiv = (int *)malloc(m * sizeof(int));

            arrayCopy(key, Ldiv, h);
            arrayCopy(key+h, Rdiv, m);
 
            mergeSort(h, Ldiv);
            mergeSort(m, Rdiv);
            merge(h, m, Ldiv, Rdiv, key);
 
            free(Ldiv);
            free(Rdiv);
      }
}

int main(void)
{
      int i;
      int key[KEY_SIZE];
 
      srand((unsigned int)time(NULL));

      printf("====== Before Merge sort");
      for (i=0; i<KEY_SIZE; i++) {
            if (i%20 == 0)
                  puts("\n");
            key[i] = rand() % 100;  // KEY_SIZE 만큼의 무작위 수 생성
            printf("%d ", key[i]);
      }

      mergeSort(KEY_SIZE, key);   // 합병정렬

      printf("\n\n====== After Merge sort");
      for (i=0; i<KEY_SIZE; i++) {
            if (i%20 == 0)
                  puts("\n");
            printf("%d ", key[i]);
      }
      return 0;
}

위 구현된 합병정렬을 살펴보면 알겠지만 합병정렬을 수행하기 위해 입력된 배열 이외의 추가적인 배열(Ldiv, Rdiv)가 사용되는 것을 알 수 있다. 따라서 mergeSort 함수가 수행될 때 마다 배열들이 추가적으로 할당된다.

최상위의 두 배열의 아이템 개수는 n개이다. 처음 재귀호출을 하게 되면 이는 n/2개가 되고, 다음에는 n/4개가 된다. 평균적으로 재귀 호출시 두 배열의 아이템 개수는 바로 전 아이템 개수 합의 반이 된다. 따라서 추가적으로 만들어지는 배열아이템의 총 수는 n(1 + 1/2 + 1/4 + ... ) = 2n 이 된다.

위의 예제가 분할정복법(Divide-and-Conquer)를 설명하기에는 적합할지 모르지만 메모리 사용에서는 상당히 비 효율적이다. 따라서 제자리정렬(in-place sort)로 다시 구현해 보자. 제자리정렬은 입력을 저장하는 데 필요한 장소 이외의 추가적인 저장장소를 사용하지 않는 정렬 알고리즘이다.

다음은 제자리 정렬로 구현한 합병정렬이다.

void merge(int low, int mid, int high)
{
      int i, j, k;

      for (i=low; i<=high; i++) {
            temp[i] = key[i];       // 임시배열로 해당 키 값을 복사한다.
      }

      i = low; j = mid+1; k = low;

      while (i <= mid && j <= high)
            if (temp[i] < temp[j])
                  key[k++] = temp[i++];   // 다시 원래 배열로 키 값을 크기에 맞게 복사한다.
            else
                  key[k++] = temp[j++];

      while (i <= mid)              // 키값에 따라 복사되고 난 나머지 키들을 복사한다.
            key[k++] = temp[i++];

}

void mergeSort(int low, int high)
{
      int mid;

      if (low < high) {
            mid = (low + high)/2;
            mergeSort(low, mid);
            mergeSort(mid+1, high);
            merge(low, mid, high);
      }
}

출처: http://proneer.tistory.com/entry/Sort-합병-정렬Merge-Sort