병합정렬(Merge Sort)

병합정렬(Merge Sort)

퀵 정렬과 같이 병합정렬도 '분할 정복' 알고리즘이다. 

 

시간복잡도가 O(N * logN)을 가진다.

 

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

 

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

7 6 5 8 3 5 9 1

---

병합정렬은 퀵 정렬과 다르게 피벗 값이 없다. 항상 반으로 나누기 때문이다. 바로 이 특징이 단계의 크기가 logN이 되도록 만들어준다.

 

아래는 병합정렬 과정을 그림으로 나타낸 것이다. 1단계에서 2개씩 정렬을 한다. 즉, 7과 6을 묶어 7과 6중 작은 숫자가 앞으로 오게 정렬이 된다. 5와 8을 묶어 5가 앞으로 오고 8이 뒤로가게 정렬을 한다.  병합 정렬은 이미 정렬이 되어 있는 상태에서 다시 새롭게 정렬이 된 상태를 만드는 것이다. 시작 단계에서 하나씩 정렬이 되어있고 1단계에서 2개씩 묶어 정렬을 하고 2단계에서 4개씩 묶어 정렬을 수행한다. 4개 안에서 정렬이 된다. 3단계에서 최종 정렬된 상태로 만든다.

 

병합정렬이 어떻게 N * logN이 되는 지 보자. 데이터 개수가 8개이다. N은 8이다. 너비는 8이고 높이는 3이다. 높이가 3인 이유는 log밑2 8은 3이기 때문이다. 처리하는 데이터 개수가 1단계에서는 2^1, 2단계에서는 2^2, 3단계에서는 2^3이 된다. 그래서 N * logN이 되는 것이다.

 

병합정렬은 합치는 순간에 정렬을 수행한다. 1단계에서 2단계로 넘어갈 때 정렬횟수는 N이다.

 

아래 그림을 보면 이미 정렬이 수행된 상태에서 정렬을 수행하기 때문에 N번만 소요된다. i와 j의 위치를 비교해서 더 작은 값이 k에 위치한다. 6,7 과 5,8은 이미 정렬이 된 상태이고 데이터를 하나씩 총 4번 읽는 과정으로 정렬이 수행된다. 즉, 데이터 개수 N개 만큼만 수행하면 된다. 그 다음 으로 j를 8로 한칸옮겨 6과 8을 비교해서 더 작은 값인 6이 들어간다. 그 다음 i를 1증가시켜 7과 8을 비교해 7이 들어간다.

 

병합정렬은 기존의 데이터를 담을 추가적인 배열공간이 필요한 점에서 메모리 활용이 비효율적인 문제가 있다. 

 

병합정렬의 시간복잡도는 O(N * logN)이다.

 

병합정렬은 일반적인 경우 퀵 정렬보다 느리지만 어떠한 상황에서도 정확히 O(N * logN)을 보장할 수 있다.

 

#include <stdio.h>

 

//상수로 선언해야 한다. array 배열선언시 대괄호 안에 변수로 사용하기 위해.

const int NUMBER = 8;

//정렬 배열은 반드시 전역 변수로 선언.

//단계별 정렬 수행 시 추가적인 배열이 필요한데 이 것을

//필요할 때마다 배열을 생성하면 비효율적이기 때문이다.

int sorted[8];

int array[NUMBER] = {7, 6, 5, 8, 3, 5, 9, 1};

 

void show(){

           for(int i = 0; i < NUMBER; i++){

                      printf("%d ", array[i]);

           }

}

 

//부분배열을 이용해 새롭게 정렬된 배열을 만드는 함수.

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++){

                                 sorted[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, middle + 1, n);

                      merge(a, m, middle, n);

           }

          

           //1.

           //0 7

           //0 3

           //4 7

           //0 3 7

          

           //2.

           //0 3

           //0 1

           //2 3

           //0 1 3

          

           //3.

           //4 7

           //4 5

           //6 7

           //4 5 7

          

           //4.

           //0 1

           //0 0

           //1 1

           //0 0 1

          

           //5.

           //2 3

           //2 2

           //3 3

           //2 2 3

          

           //6.

           //4 5

           //4 4

           //5 5

           //4 4 5

          

           //7.

           //6 7

           //6 6

           //7 7

           //6 6 7

}

 

int main(void){

           mergeSort(array, 0, NUMBER -1);

           show();

           return 0;

}