[Algorithms] 2.3 Mergesort

in Devlog on Algorithm


저자 Dasgupta의 Algorithms을 해석하면서 정리한 글입니다.

2.3 Mergesort

병합 정렬은 대표적인 ‘분할 정복(Divide and conquer) 방법’을 채택한 알고리즘입니다.

병합 정렬 알고리즘은 아래와 같은 단계로 진행됩니다.

1) 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봅니다. 2) 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나누어 줍니다. 3) 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬합니다. 4) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병합니다.

병합 정렬 알고리즘 예제

예를 들어 더 자세히 살펴보겠습니다.
배열에 27, 10, 12, 20, 25, 13, 15, 22가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해보겠습니다.

2개의 정렬된 리스트를 합병(merge)하는 과정

i.   2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮깁니다.
ii.   둘 중에서 하나가 끝날때까지 이 과정을 반복합니다.
iii.   만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사합니다.
iv.   새로운 리스트(sorted)를 원래의 리스트(list)로 옮겨줍니다.

img

전체적인 흐름은 다음과 같이 이루어집니다. img

병합 정렬의 과정을 분할 정복 방법으로 나타내면 다음과 같습니다.

  • 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.
  • 정복(Conquer): 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용합니다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병시킵니다.

병합 정렬 코드

병합 정렬 알고리즘을 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]);
  }
}

병합 정렬의 시간복잡도

img 결과만 먼저 말씀드리면, 병합 정렬의 Depth는 $log_2n$이며, Width는 $n$입니다.
이들을 각각 곱할 경우, 시간 복잡도는 $O(n*logn)$이 됩니다.

  • 순환 호출의 깊이 (합병 단계의 수)
    • 레코드의 개수 n이 2의 거듭제곱이라고 가정$(n=2^k)$했을 때, $n=2^3$의 경우, $2^3$ -> $2^2$ -> $2^1$ -> $2^0$ 순으로 줄어들어 순환 호출의 깊이가 3이 됩니다.
    • 이것을 일반화하면 $n=2^k$의 경우, $k=log_2n$임을 알 수 있습니다.
  • 각 합병 단계의 비교 연산
    • 크기 1인 부분 배열 2개를 합병하는 데는 최대 2번의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 $2*4=8$번의 비교 연산이 필요합니다.
    • 다음 단계에서는 크기 2인 부분 배열 2개를 합병하는 데 최대 4번의 비교 연산이 필요하고, 부분 배열의 쌍이 2개이므로 $4*2=8$번의 비교 연산이 필요합니다.
    • 마지막 단계에서는 크기 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하고, 부분 배열의 쌍이 1개이므로 $8*1=8$번의 비교 연산이 필요합니다.
    • 이것을 일반화하면 하나의 합병 단계에서는 최대 n번의 비교 연산을 수행함을 알 수 있습니다.
    • 비교연산의 횟수가 이해되지 않으면 여기 링크를 참조하시면 됩니다.
  • 최종적으로 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = $nlog_2n$

병합 정렬은 어떤 상황에서도 정확히 $O(n*logn)$을 보장할 수 있다는 점에서 효율적인 알고리즘으로 손꼽힙니다.

반복 병합 정렬(Iterative Merge Sort)

입력 리스트를 길이가 1인 n개의 정렬된 서브리스트로 간주합니다.

  • 반복 합병 정렬 단계
    • 첫번째 합병 단계 : 리스트들을 쌍으로 합병하여 크기가 2인 n/2개의 리스트를 얻습니다.
      • n이 홀수면 리스트 하나는 크기가 1이 됩니다.
    • 두번째 합병 단계 : n/2개의 리스트를 다시 쌍으로 합병하여 n/4개의 리스트를 얻습니다.
    • 합병 단계는 하나의 서브 리스트가 남을 때까지 계속됩니다.
      • 한 번 합병할 때마다 서브 리스트의 수는 반으로 줄어듭니다.

예로 Input List로 (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)가 있습니다.

그럼 다음과 같이 정렬이 이루어집니다.

img

Reference

  1. Algorithms - Dasgupta
  2. https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
  3. https://velog.io/@cham/Sort-%ED%95%A9%EB%B3%91-%EC%A0%95%EB%A0%ACmerge-sort
  4. https://blog.naver.com/ndb796/221227934987



© 2020. by GeonKimdcu

Powered by aiden