[정렬] 병합 정렬 ( Merge Sort)

오늘은 정렬 방법 중에 하나인 '병합 정렬'에 대해서 알아봅시다!

분할 정복에 대해 간단히 설명하면, 하나의 큰 덩어리를 작게 분할하여 해결하고, 이 작은 덩어리들을 묶어서 또 다시 해결을 하다보면 최종적으로 자신이 원하는 답을 찾는다는 것입니다.

어디서 많이 들었던 소리이지 않습니까?! 바로 재귀 함수에서 나왔던 개념입니다!

따라서, 분할 정복은 재귀를 통해서 해결하는 경우가 많습니다.

어쨌든, 이 병합 정렬도 분할 정복을 통해 정렬하는 방법입니다.

방법은 간단합니다! 데이터를 한 조각이 남을 때까지 계속해서 쪼개고, 쪼개고, 또 쪼갭니다.

그리고 쪼개진 것들끼리 정렬을 하고, 이를 이용해서 만들어진 조금 큰 조각을 또 정렬을 하는 방법입니다!

그림으로 확인해봅시다!

그림에서 처럼 우선 데이터를 반 씩 쪼갭니다. 그리고, 쪼개진 부분들을 정렬합니다.

작게 쪼개진 부분들은 정렬되어 있는 결과이기 때문에, 쪼개진 두 개의 데이터들의 앞부분이 더 작은 값을 차례대로 넣어주면 다시 정렬된 더 큰 조각이 됩니다. 마지막에는 모두 정렬된 데이터가 될 것입니다.

반으로 쪼개는 것이므로, 데이터가 1개로 쪼개지기 까지의 높이는

이고, 각 층마다 데이터는 n 번의 비교를 하기 때문에 시간복잡도는이 됩니다. 

이 정도만 되면 실제로 사용될 수 있는 상당히 괜찮은 알고리즘이라고 할 수 있습니다!

참고로, 병합정렬은 정렬된 데이터의 중간 값을 보관하기 위해서 별도의 저장공간이 하나 더 필요합니다.

 

아래는 이를 구현하기 위한 병합 정렬 코드입니다.

#include<stdlib.h>
#include<time.h>
 
int datas[100];
int temp[100];
 
void merge(int l, int m, int r)
{
    int i = l, j = m + 1, k = l;
 
    while (i <= m && j <= r)
    {
        if (datas[i] < datas[j])
        {
            temp[k++] = datas[i++];
        }
        else
        {
            temp[k++] = datas[j++];
        }
    }
 
    while(i <= m) temp[k++] = datas[i++];
    while (j <= r) temp[k++] = datas[j++];
 
    for (int i = l; i <= r; i++) datas[i] = temp[i];
}
 
void mergeSort(int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);
 
        merge(l, m, r);
    }
}
 
 
int main()
{
    srand(time(NULL));
 
    for (int i = 0; i < 10; i++)
    {
        int len = rand() % 100 + 1;
 
        printf("len : %d\n", len);
        printf("before\n");
        for (int i = 0; i < len; i++)
        {
            datas[i] = rand() % 100;
            printf("%2d ", datas[i]);
        }
        printf("\n");
 
        mergeSort(0, len - 1);
 
 
        printf("after\n");
        for (int i = 0; i < len; i++)
        {
            printf("%2d ", datas[i]);
        }
        printf("\n\n");
    }
    
    return 0;
}
 

코드의 핵심은 이 부분입니다.

void merge(int l, int m, int r)

{

    int i = l, j = m + 1, k = l;

 

    while (i <= m && j <= r)

    {

        if (datas[i] < datas[j])

        {

            temp[k++] = datas[i++];

        }

        else

        {

            temp[k++] = datas[j++];

        }

    }

 

    while(i <= m) temp[k++] = datas[i++];

    while (j <= r) temp[k++] = datas[j++];

 

    for (int i = l; i <= r; i++) datas[i] = temp[i];

}

 

void mergeSort(int l, int r)

{

    if (l < r)

    {

        int m = (l + r) / 2;

        mergeSort(l, m);

        mergeSort(m + 1, r);

 

        merge(l, m, r);

    }

}

mergeSort()부분을 통해서 데이터들을 작게 쪼갠 뒤에, merge를 통해서 직접 데이터를 정렬합니다.

작은 조각은 이미 정렬된 상태이므로, 작은 조각의 앞 부터 차례대로 작은 것을 넣어줍니다.

만약, 한 쪽이 먼저 전부 들어간다면, 나머지 값은 차례대로 뒤쪽에 넣어주면 됩니다.

마지막으로, 임시 공간에 정렬된 상태이므로 원래 있는 곳에다 다시 옮겨주는 추가 작업이 필요합니다.

아래는 병합 정렬을 시행하고 난 뒤의 결과 중 하나입니다! 깔끔하게 잘 정렬된 것을 볼 수 있습니다.