[자료구조] 합병정렬(Merge Sort) - C언어

 

https://www.geeksforgeeks.org/merge-sort/

#합병정렬

- Merge sort는 분할정복법을 사용하여 정렬하는 알고리즘이다.

- 분할 단계: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

- 정복 단계: 각각의 작은 문제들을 순환적으로 해결

- 합병 단계: 작은 문제들의 해를 합하여(merge) 원해 문제에 대한 해를 구함

 

#Pseudo code

function mergeSort(list, left, right)
	middle = (left+right) / 2 #l과 r의 중간 지점 계산
    mergeSort(list, left, mid) #전반부 정렬
	mergeSort(list, mid+1, right) #후반부 정렬
	merge(list, left, mid, right) #합병

 

#시간 복잡도

 - 데이터 크기가 n 일때, mergeSort 는 n 을 절반으로 나누는 작업을 반복하므로 2^x = n /
log2^x = log2n / x = log n / 총 log n 번 수행됨
 - 분할된 배열을 다시 merge 할 때 sort 과정은 n에 비례적으로 수행되므로 O(n)만큼 수행
병합 과정이 log n번 수행되므로 최종 시간복잡도는 O(n log n)

 

1. 분할 단계

 - 비교 연산과 이동 연산이 수행되지 않는다.

2. 합병 단계

 - 비교 횟수

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

 - 순환 호출의 깊이(합병 단계의 수)

• 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, 
• n=2^3의 경우, 2^3-> 2^2 -> 2^1 -> 2^0 순으로 줄어듦 → 순환 호출의 깊이 = 3
• n=2^k의 경우, k(k=log₂n)

 - 각 합병 단계의 비교 연산

• 크기 1인 부분 배열 2개를 합병하는 데는 최대 2번의 비교 연산이 필요하다.
• 부분 배열의 쌍이 4개이므로 24=8번의 비교 연산이 필요하다.
• 다음 단계에서는 크기 2인 부분 배열 2개를 합병하는 데 최대 4번의 비교 연산이 필요하다.
• 부분 배열의 쌍이 2개이므로 42=8번의 비교 연산이 필요하다.
• 마지막 단계에서는 크기 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하다.
• 부분 배열의 쌍이 1개이므로 8*1=8번의 비교 연산이 필요하다. 
• 하나의 합병 단계에서는 최대 n번의 비교 연산을 수행함을 알 수 있다.
• 최대 n번 

 - 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlog₂n

 

#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]);
  }
}

 

(참고 사이트)

www.geeksforgeeks.org/merge-sort/

ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/

excelsior-cjh.tistory.com/47

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