병합 정렬(Merge Sort)

병합 정렬(Merge-Sort)

- 배열의 원소를 완전 분해한 후에 다시 병합하며 정렬하는 방식

- 항상 O(n log n)의 복잡도를 가진다

1. 동작 원리

(1) 주어진 배열을 2개의 파티션으로 나눈다.

(2) 하나의 원소가 남을 때까지 (1)의 과정을 재귀적으로 반복한다.

(3) 완전 분해한 원소를 다시 병합하며 정렬을 수행한다.

 

2. 함수 설명

- merge_sort() :  동작원리 (1)과 (2)에 해당하는 기능을 수행한다.

- merge() : 동작원리 (3)에 해당하는 기능을 수행한다.

 

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

#define MAX  10 // size of array
#define INF  10000 // infinity value

void display_elements( int *, int);
void merge_sort( int *, int, int);
void merge(int *, int, int, int);

int main( void)
{
 int arry[MAX]  = { 0,};
 int count   = 0;
 int size   = 0;

 srand( time(NULL)); // used to init random

 size  = sizeof(arry)/4;

 // init elements of array with random numbers
 for( count = 0 ; count < size ; count ++)
 {
  arry[count]  = rand()%(MAX*10);
 }

 // display elements of array
 printf("Before sorting : ");
 display_elements( arry, size);

 // call Sorting
 merge_sort( arry, 0, size-1);

 // output result
 printf("\n After sorting : ");
 display_elements( arry, size);

 return 0;
}

void display_elements( int *ar, int s)
{
 int count  = 0;

 for( count = 0 ; count < s ; count ++)
 {
  printf("%4d", ar[count]);
 }
}

void merge_sort( int *A, int start, int end)
{
 int center  = (start + end) / 2;

 if( start < end)
 {
  // devide the array into two sub arrays
  merge_sort( A, start, center);
  merge_sort( A, center+1, end);

  // conquer sub arrays.
  merge( A, start, center, end);
 }
}

void merge( int *A, int start, int center, int end)
{
 int left = center - start + 2; // get a size of sub-array on the left
 int right = end - center + 1; // get a size of sub-array on the right
 int l, r, i;
 int *L, *R;

 L = (int*)malloc(sizeof(int) * left); // allocate the memory as much as the Left needs
 R = (int*)malloc(sizeof(int) * right); // allocate the memory as much as the Right needs

 l = r = 0; // reset starting point

 for( i = start ; i <= center ; i ++)
 {
  L[l++] = A[i]; // move elements that stored in the A to L
 }
 for( i = center + 1 ; i <= end ; i ++)
 {
  R[r++] = A[i]; // move elements that stored in the A to R
 }

 L[l] = INF; // need it to notify that the L is empty
 R[r] = INF; // need it to notify that the L is empty

 l  = r = 0;

 /*
  sorting process
 */
 for( i = start ; i <= end ; i ++)
 {
  if( L[l] <= R[r])
  {
   A[i] = L[l++];
  }
  else
  {
   A[i] = R[r++];
  }
 }

 free(L);
 free(R);
}