[ 알고리즘 / 정렬 ] 분할 정복 알고리즘 / 병합 정렬(Merge Sort)

분할 정복 알고리즘은 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘이다.

 

분할 정복 알고리즘의 핵심은 '문제를 잘게 쪼개기'라고 할 수 있다. 문제를 쪼개는 방법에 대해서는 정해진 공식이나 규칙은 없다. 이것은 알고리즘을 개발하는 개발자의 창의력에 달려있는 것이다.

 

다만 분할 정복 알고리즘을 설계하는 대강의 요령은 있다. 그 요령은 다음과 같다.

 

① 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.

② 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 ①을 수행한다.

                             그렇지 않다면 하위 문제를 푼다.

③ 결합(Combine) : ②과정에서 정복된 답을 취합한다.

 

분할 정복 알고리즘으느 '문제를 나누는 것'이 가장 중요하다. 문제를 제대로 나누기만 한다면 정복(해결)하는 것은 아주 쉽기 때문이다.

분할 정복 기법으로 문제를 나눌 때 생기는 각 하위 문제는 완전히 독립적이다. 이 사실은 곧 큰 문제로부터 나뉘어 떨어진 문제들은 여러 프로세스, 네트워크 상의 여러 컴퓨터에 의해 병렬 처리가 가능하다는 것을 의미한다.

 

하지만 분할 정복이 무조건 장점만 있는 것은 아니다. 분할 정복 기법에서 함수의 재귀 호출이 자연스럽게 떠오를 텐데, 이 때문에 문제를 잘게 나눔으로써 얻어진 알고리즘의 효율성을 재귀 호출 비용이 깎아내린다는 단점이 있다.

 

병합 정렬(Merge Sort)

" 나누고 합쳐라! "

병합 정렬은 주어진 배열을 모두 분할한 후, 정렬해 나가면서 결합하는 것이다.

 

다음과 같은 순서로 동작한다.

 

① 정렬할 데이터 집합을 반으로 나눈다. (분할)

② 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 ①을 반복한다.

③ 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다.

     단, 병합할 때 데이터 집합의 원소는 순서에 맞추 정렬한다. (정복/결합)

④ 데이터 집합이 다시 하나가 될 때까지 ③을 반복한다.

<분할>

데이터 집합을 반으로 나누기 위해 Mid값을 찾고

Start ~ Mid

Mid+1 ~ End

두 구간으로 나누어준다.

 

하위 데이터 집합이 1개가 될 때까지 반복한다.

 

void MergeSort(int DataSet[], int StartIndex, int EndIndex)
{
    if(StartIndex > EndIndex) return;
    
    int MiddleIndex = (StartIndex + EndIndex) / 2; // 절반으로 나누기 위해 중간 값 찾기
    
    MergeSort(DataSet, StartIndex, MiddleIndex); // 시작 ~ 중간
    MergeSort(DataSet, MiddleIndex + 1, EndIndex); // 중간+1 ~ 끝
    
    Merge(DataSet, StartIndex, MiddleIndex, EndIndex); // 다시 합치기
}

<정복/결합>

합치는 알고리즘은 알겠지만, '정렬'을 어떻게 수행해야 할까? 그것도 두 데이터 집합을 하나로 합치면서 정렬해야 한다.

 

① 두 데이터 집합을 합한 것만큼의 비어 있는 데이터 집합을 마련한다.

② 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 새 데이터 집합에 추가한다.

     그리고 새 데이터 집합에 추가된 요소는 원래 데이터 집합에서 삭제한다.

③ 양쪽 데이터 집합이 빌 때까지 ②를 반복한다.

 

void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex)
{
    int Length = EndIndex - StartIndex + 1;
    int* Destination = (int*) malloc(sizeof(int) * Length); // 현재 데이터 집합 크기만큼 임시 배열 만들기
    
    int LeftIndex = StartIndex;
    int RightIndex = MiddleIndex + 1;
    int DestIndex = 0;
    
    while(LeftIndex <= MiddleIndex && RightIndex <= EndIndex)
    {
        if(DataSet[LeftIndex] < DataSet[RightIndex]) // 왼쪽 배열의 값이 더 작으면
        {
            Destination[DestIndex] = DataSet[LeftIndex]; // 왼쪽 배열의 데이터부터 넣어준다
            LeftIndex++;
        }
        else                                         // 오른쪽 배열의 값이 더 작으면
        {
            Destination[DestIndex] = DataSet[RightIndex]; // 오른쪽 배열의 데이터부터 넣어준다
            RightIndex++;
        }
        DestIndex++;
    }
    
    while(LeftIndex <= MiddleIndex) // 오른쪽 배열이 먼저 끝나서, 왼쪽 배열 데이터가 남은 경우
    {
        Destination[DestIndex++] = DataSet[LeftIndex++];
    }
    
    while(RightIndex <= EndIndex) // 왼쪽 배열이 먼저 끝나서, 오른쪽 배열 데이터가 남은 경우
    {
        Destination[DestIndex++] = DataSet[RightIndex++];
    }
    
    DestIndex = 0;
    for(int i = StartIndex; i <= EndIndex; i++)
    {
        DataSet[i] = Destination[DestIndex++]; // 기존 배열에 정렬된 데이터를 넣어준다.
    }
    
    free(Destination);
}

 

 

시간복잡도

퀵 정렬과 비슷하게 병합정렬도 반으로 나누는 과정이 필요하다. 즉, 퀵 정렬의 이상적인 경우와 시간복잡도가 동일하다.

일반적인 경우 병합정렬은 퀵정렬과 같이 시간복잡도가 nlogn이다. 

 

최악의 경우는?

퀵정렬의 최악의 경우는 Pivoit을 잘못 선택했을 때이다. 따라서 N^2의 시간복잡도를 갖게 된다.

하지만 병합정렬의 경우 무조건 반씩 나누기 때문에 이런 최악의 경우가 존재하지 않는다.

즉, 병합정렬은 퀵 정렬과 다르게 최악의 경우도 nlogn이다.

 

그렇다면 무조건 병합정렬이 좋을까?

아니다. 병합정렬은 임시적인 배열을 만들 추가적인 공간이 필요한 단점이 있다.

따라서 그만큼의 메모리를 추가적으로 할당해줘야하는 큰 단점이 있다.

 

 

전체 코드

#include <stdio.h>
#include <stdlib.h>

void MergeSort(int DataSet[], int StartIndex, int EndIndex);
void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex);


void MergeSort(int DataSet[], int StartIndex, int EndIndex)
{
    if(StartIndex > EndIndex) return;
    
    int MiddleIndex = (StartIndex + EndIndex) / 2; // 절반으로 나누기 위해 중간 값 찾기
    
    MergeSort(DataSet, StartIndex, MiddleIndex); // 시작 ~ 중간
    MergeSort(DataSet, MiddleIndex + 1, EndIndex); // 중간+1 ~ 끝
    
    Merge(DataSet, StartIndex, MiddleIndex, EndIndex); // 다시 합치기
}

void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex)
{
    int Length = EndIndex - StartIndex + 1;
    int* Destination = (int*) malloc(sizeof(int) * Length); // 현재 데이터 집합 크기만큼 임시 배열 만들기
    
    int LeftIndex = StartIndex;         // 왼쪽 배열의 시작은 시작 인덱스
    int RightIndex = MiddleIndex + 1;   // 오른쪽 배열의 시작은 중간 인덱스 + 1
    int DestIndex = 0;
    
    while(LeftIndex <= MiddleIndex && RightIndex <= EndIndex)
    {
        if(DataSet[LeftIndex] < DataSet[RightIndex]) // 왼쪽 배열의 값이 더 작으면
        {
            Destination[DestIndex] = DataSet[LeftIndex]; // 왼쪽 배열의 데이터부터 넣어준다
            LeftIndex++;
        }
        else                                         // 오른쪽 배열의 값이 더 작으면
        {
            Destination[DestIndex] = DataSet[RightIndex]; // 오른쪽 배열의 데이터부터 넣어준다
            RightIndex++;
        }
        DestIndex++;
    }
    
    while(LeftIndex <= MiddleIndex) // 오른쪽 배열이 먼저 끝나서, 왼쪽 배열 데이터가 남은 경우
    {
        Destination[DestIndex++] = DataSet[LeftIndex++];
    }
    
    while(RightIndex <= EndIndex) // 왼쪽 배열이 먼저 끝나서, 오른쪽 배열 데이터가 남은 경우
    {
        Destination[DestIndex++] = DataSet[RightIndex++];
    }
    
    DestIndex = 0;
    for(int i = StartIndex; i <= EndIndex; i++)
    {
        DataSet[i] = Destination[DestIndex++]; // 기존 배열에 정렬된 데이터를 넣어준다.
    }
    
    free(Destination);
}

int main(void)
{
    int DataSet[] = { 334, 6, 4, 2, 3, 1, 5, 117, 12, 34 };
    int Length = sizeof DataSet / sizeof DataSet[0];
    
    MergeSort(DataSet, 0, Length-1);
    
    for(int i = 0; i < Length; i++)
    {
        printf("%d ", DataSet[i]);
    }
    return 0;
}