알고리즘 [Algorithm] - 병합 정렬 Merge Sort(5) (C,Python)

병합정렬

  이번에는 병합 정렬에 대해 알아보자. 병합정렬도 퀵정렬과 마찬가지로 대표적인 '분할정복' 방법을 채택한 알고리즘이다. 따라서 결과적으로 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다.

 

  다만 퀵 정렬은 최악의 경우 O(N^2)의 시간복잡도를 가지지만, 병합정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N*logN)을 보장한다. 

 

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

7 6 5 8 3 5 9 1

---

병합정렬은 하나의 큰 문제를 두개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다. 즉 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬하는 것이다. 

  퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징이 있고, 때문에 단계의 크기가 log N이 되도록 만들어준다.

 

7   6   5   8   3   5   9   1

67   58   35   19

5678   1359

13556789

 

  문제의 7 6 5 8 3 5 9 1은 모두 크기가 개별인 배열로, 즉 크기가 1인 배열 상태로 시작한다. 첫번째 단계에서는 배열의 크기가 2개이다. 이때 개별의 원소들이 두개로 합쳐지는 순간 정렬이 된다. 따라서 7 / 6 은 67로, 5 / 8 은 58로... 다음 단계에서도 2개의 원소로 이루어진 배열들이 정렬되면서 합쳐진다. 67 / 58 이 5678로, 35 / 19가 1359로...

 

  합치는 갯수가 2배씩 증가한다는 점에서 단계의 크기는 데이터의 갯수가 N개 일때 log N을 유지하게 된다. 

따라서 병합정렬의 시간 복잡도는 O(N * log N)이 된다.

 

#include <stdio.h>
int number = 8;

int size;
int sorted[8]; // 정렬 배열은 반드시 전역변수로 선언
int count = 0;

void merge(int a[],int m, int middle, int n)){
	int i = m;
    int j = middle +1;
    int k = m;
    // 작은 순서대로 배열에 삽입
    while(i<=middle &&j<=n){
    	if(a[i] <= a[j]) {
        	sorted[k] = a[i];
            i++;
        }
        else{
        	sorted[k] = a[j];
            j++;
        }
        k++;
    }
    //남은 데이터도 삽입
    if(i>middle){
    	for(int t = j; t<=n; t++){
        	sorted[k] = a[t];
            k++;
            }
    }
    else{
    	for(int t=i;t<=middle;t++){
        	sosrted[k] = a[t];
            k++;
        }
    }
    
    //정렬된 배열을 삽입
    for(int t=m; t<=n; t++){
    	a[t] = sorted[t];
    }
}

void mergeSort(int a[], int m, int n){
	//이외의 경우는 크기가 1개인 경우
    if(m<n){
    	int middle = (m+n)/2;
        mergeSort(a,m,middle);
        mergeSort(a,midddle+1,n);
        merge(a,m,middle,n);
    }
}


int main(void){
	int array[number] = {7, 6, 5, 8, 3, 5, 9, 1};
    mergeSort(array,0,number-1);
    for(int i=0; i< number;i++){
    	printf("%d ", array[i]);
    }
}

병합 정렬을 구현할 때 정렬에 사용되는 배열은 반드시 '전역변수'로 선언해야 한다. 만약 함수 안에서 배열을 선언하게 된다면 매번 배열을 선언해야 하므로 메모리 낭비가 매우 커질 수 있기 때문이다. 따라서 기본적으로 병합정렬은 '기존의 데이터를 담을 추가적인 배열공간이 필요하다'는 점에서 메모리 활용이 비효율적이라는 문제가 있다. 하지만 어떤 상황에서도 병합정렬의 시간 복잡도는 O(N * log N)을 보장하는 점에서 효율적인 알고리즘이다.

 

 

Python

sublist = [7,4,6,5,3,2,1,9,8,10]

def merge(list1,left,right,end):
  merged = []
  l,r = left,right
  while l< right and r<=end:
    if list1[l] <=list1[r]:
      merged.append(list1[l])
      l+=1
    else:
      merged.append(list1[r])
      r+=1
  while l<right:
    merged.append(list1[l])
    l+=1
  while r<=end:
    merged.append(list1[r])
    r+=1

  l = left
  for n in merged:
    list1[l] = n
    l+=1

def mergeSort(list1,p,q):
  if p>=q:
    return
  mid = (p+q)//2
  mergeSort(list1,p,mid)
  mergeSort(list1,mid+1,q)
  merge(list1,p,mid+1,q)


print(sublist)
sorted = mergeSort(sublist,0,len(sublist)-1)
print(sublist)

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz