[Algorithm] 합병정렬 (Merge sort)

💡합병정렬 알고리즘?

• 안정정렬에 속하며, 분할 정복 알고리즘의 하나
• 분할 정복 방법 (divide and conquer)
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결
  • 대개 순환 호출을 이용하여 구현 (재귀적)
• 과정
  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
  2. 그렇지 않은 경우, 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬
  4. 두부분 리스트를 다시 하나의 정렬된 리스트로 합병

[ 합병정렬 알고리즘의 구체적인 개념 ]

• 하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
• 단계
  • 분할 (Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
  • 정복 (Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출로 다시 분할 정복 방법을 적용
  • 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병
• 합병 정렬의 과정
  • 추가적인 리스트가 필요
  • 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
  • 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

    

 

💡 합병 정렬 알고리즘의 예제

• 그림과 같은 배열이 있다고 가정하고 자료를 오름차순으로 정렬해보자.
• 2개의 정렬된 리스트를 합병(merge)하는 과정
  1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
  2. 둘중에서 하나가 끝날때까지 이 과정을 되풀이
  3. 만약 둘중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
  4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

     

 

#include <iostream>
using namespace std;
int sorted[9]; //추가적인 임시 배열 공간    


// 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;

    // 분할된 정렬리스트 두개를 합병
    while(i=<mid && j<=right){
        if(list[i]<list[j]){
            sorted[k++] = list[i++];
        }
        else{
            sorted[k++] = list[j++];
        }
    };

    // 남아 있는 것들을 일괄 복사
    if(j<=right){
        for(l=j;l<=right;l++){
            sorted[k++] = list[l];
        };
    }
    if(i<=mid){
        for(l=i;l<=mid;l++){
            sorted[k++] = list[l];
        };
    }

    // 임시배열 sorted[] 에 있는 값들을 list[]로 복사
    for(l=left;l<=right;l++){
        list[l] = sorted[l];
    };

}

// 합병 정렬
void mergeSort(int list[], int left, int right){
    int mid;

    if(left<right){
        mid = (left+right) / 2;
        mergeSort(list, left, mid);
        mergeSort(list, mid+1, right);
        merge(list, left, mid, right);
    };
}

int main(){
    int list[9] = {21, 10, 12, 20, 25, 13, 15, 22, 33};

    mergeSort(list, 0, 8);

    for(int i=0;i<9;i++){
        cout << list[i]<< " ";
    };
}

코드과정

 

---

💡 합병정렬 알고리즘의 특징

단점

• 입력을 위한 메모리 공간 (입력배열)외에 추가로 입력과 같은 크기의 공간 (임시배열)이 별도로 필요하다.
  • 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문에

장점

• 연결리스트에 있는 데이터를 정렬할 때, 퀵정렬이나 힙 정렬보다 훨씬 효율적이다. 
  • 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  • 제자리 정렬로 구현할 수 있다.

응용

• 멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화 하는데에 합병 정렬 알고리즘이 활용

 

합병 정렬의 시간복잡도

1. 분할 단계 : 비교 연산과 이동 연산이 수행되지 않는다. (중간의 인덱스 계산과 2번의 재귀호출 -> O(1))
2. 합병 단계 : 숫자의 비교 연산 횟수가 가장 중요한 요소

   

   • 순환 호출의 깊이
     • 배열의 원소개수 n이 2의 거듭 제곱이라고 가정하자 ( n = 2^k )
     • n = 2^3 일 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.
     • n = 2^k 일 경우, 순환 호출의 깊이는 k이고 k = log₂n 이다.
     • log₂n
   • 각 합병 단계의 비교 연산
     • 배열 A와 B의 크기가 각각 a,b라면, 최대 비교 횟수 = (a+b-1)
     • 각 층을 살펴보면 모든 숫자가 합병에 참여
     • 합병은 입력 크기에 비례하므로 각 층에서 수행된 비교횟수는 O(n)
   • 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlog₂n
   • 이동 횟수 (근데,, 결과가 똑같아서 인지 교수님께서는 따로 이부분에 대해서 말씀 없으셨음 하지만 정리는 해두겠다!)
     • 순환 호출의 깊이 (합병 단계의 수) : log₂n
     • 각 합병 단계의 이동 연산 : 임시 배열에 복사했다가 다시 가져와야 되므로 이동연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n 번 발생
     • 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 이동연산 =. 2nlog₂n
   • T(n) = nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)