병합정렬 알고리즘

병합 정렬(merge sort)은 합병정렬으로도 불리며 시간 복잡도 $O(nlogn)$ 를 가지는 굉장히 빠른 정렬 알고리즘이다.

 

과정은 다음과 같다.
1. 분할

2. 정복

3. 결합

4. 복사

 

각 과정에 대해 하나씩 설명해 보겠다.

가장 먼저 분할은 정렬되지 않은 배열을 두 부분으로 잘라서 두 개의 부분 배열로 분할하는 과정이다.

만약 배열의 원소 개수가 홀수인 경우에는 크기가 비슷하도록 분할한다. 9개면 4개, 5개로 분할할 수 있다.

 

두 번째 과정은 정복이다.

정복은 분할한 각 부분 배열을 재귀적으로 병합 정렬하는 과정이다.

즉, 분할한 두 개의 배열에 대하여 또다시 분할, 정복, 결합, 복사를 거치도록 하는 것이다.

 

분할, 정복 두 과정을 c언어 코드로 설명하자면 다음과 같다.

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); 
    .
    .
    .
  }
}

정렬해야하는 배열을 list로 놓고 정렬해야 하는 부분의 처음 인덱스, 끝 인덱스를 각각 left, right로 놓았다.

mid에 left와 right의 산술평균을 대입하고 left~mid인 배열, mid+1, right인 배열 두 개로 분할한 후 정복한 과정이다.

 

세 번째 과정은 결합이다.

두 부분의 배열을 하나의 임시 배열에 병합한다.

 

결합할 때의 과정은 다음과 같다.(오름차순 정렬일 때)

1. 두 개의 배열을 첫 번째 원소부터 하나씩 비교하여 두 개의 배열 값 중에서 작은 값을 임시 배열에 저장한다.

2. 두 개의 배열 중 하나를 모두 옮길 때까지 이 과정을 반복한다.

3. 만약 두 배열중 하나의 배열이 모두 옮겨지게 되면 나머지 배열의 값들을 모두 임시 배열로 옮긴다.

 

이 과정을 c언어 코드로 설명하면 다음과 같다.

int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 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];
  }

i> mid는 왼쪽 부분 배열이 모두 옮겨지는 상황이고, j> right는 오른쪽 부분 배열이 모두 옮겨지게 되는 상황이다.

따라서 둘 중 하나가 모두 옮겨질 때까지 while문을 반복하고 난 다음 둘 중 다 옮겨지지 않은 배열이 있는지 확인하여 for문으로 옮겨준다.

 

 

네 번째 과정은 복사이다.

복사는 임시 배열에 저장해둔 결과를 원래 배열에 옮기는 과정이다.

 

이 과정을 c언어 코드로 설명하면 다음과 같다.

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

원래 배열인 list[]에 임시배열인 sorted[]배열의 값을 하나씩 옮겨주는 코드이다.

 

 

 

병합 정렬의 모든 과정을 c언어 코드로 옮기면 다음과 같다.

# include <stdio.h>
# define MAX_SIZE 8
int sorted[MAX_SIZE] // 추가적인 공간이 필요

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 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 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {21, 10, 12, 20, 25, 13, 15, 22};

  // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
  merge_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
//출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

-자료 참고, 출처

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://blog.naver.com/ndb796/221227934987