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

이번 글에서는 MergeSort(병합정렬 / 합병정렬 / 머지소트) 에 대해서 다뤄보겠다.

먼저 왜 병합정렬일까?? 병합 이라는 말은 '합친다'라는 말이다. 즉, 모든 과정을 이해하고 나면 알겠지만 주어진 배열을

모두 분리 한 후에 다시 정렬 하면서 합치는 방식이라서 병합 정렬이다.

간단하게 한 가지만 더 말하자면 Merge Sort는 '임시저장공간'을 활용해서 배열을 다시 합치는 방식이다.

Merge정렬의 동작 원리부터 알아보자.

1. 배열의 크기가 1이 될 때까지 계속 반씩 나눠준다.

2. 다 나눠 준 후에, 인접한 값들끼리 정렬하면서 합쳐준다.

말로 적다보니 굉장히 간단해 보이긴한다... 구체적으로 알아보도록 하자..

먼저 배열을 반씩 나눠 줘야 한다. 예를 들어서 배열이 총 8칸이 있다면 다음과 같이 나눠주는 것이다.

이 후 다시 인접한 칸들끼리 비교하면서 합쳐주면 되는 것이다. 다음과 같이 !

우리는 이 과정에서, Left / Mid / Right의 3개의 값을 가지고 연산을 하게 된다.

왜냐하면 어떻게 보면 우리는 다 분리되어 있는 각각의 배열을 합치는 연산을 하게 된다. 쉽게 이야기 하면

분리되어 있는 왼쪽 배열과 오른쪽 배열을 합쳐야 되는 것이다. 진행 순서는 다음과 같다.

1. Left ~ Right범위에 있는 모든 값들을 임시 배열에 옮겨 준다.

2. 왼쪽 배열의 Index를 가르키는 값과 오른쪽 배열의 Index를 가르키는 값을 비교하면서 원본의 배열에 합쳐준다.

    - 이 때, 원본 배열의 Index를 가르키기 위한 값도 필요하다.

    - 즉, Left_Index, Right_Index, Index 총 3개의 Index를 가르키는 값이 필요하게 된다.

이 때, 왼쪽 배열의 범위는 Left ~ Mid가 되는 것이고, 오른쪽 배열의 범위는 Mid + 1 ~ Right 가 되는 것이다.

이 값들이 어떻게 적용되는지 구체적으로 그림을 통해서 알아보자.

위와 같은 배열이 존재할 때, 배열의 크기가 1이 될 때 까지 반씩 나눴다고 생각해보자. 그러면 배열이 다음과 같은 형태일

것이다.

여기서 합쳐지는 과정을 한번 보자. 가장 먼저, [ 6 , 4 ], [ 1 , 7 ], [ 2 , 5 ], [ 0 , 9 ] 가 합쳐지게 된다. 다음과 같이 !

가장먼저 [ 6 ] 과 [ 4 ] 를 한번 보자. 여기서 왼쪽 배열은 [ 6 ]이고 오른쪽 배열은 [ 4 ] 이다.

이 때의 Left = 0 , Mid = 0 , Right = 1일 것이다.

즉, 왼쪽 배열의 범위는 0 ~ 0까지 이고 Right배열의 범위는 1 ~ 1이 될 것이다.

( 왜냐 하면 왼쪽 배열의 범위는 Left ~ Mid 이고 오른쪽 배열의 범위는 Mid + 1 ~ Right 이므로 ! )

위에서도 간단히 말했지만, MergeSort에서는 임시저장 공간이 필요하다.

즉, 분할되어 있는 배열에서 정렬하고자 하는 범위에 있는 값들을 임시저장공간에 넣어둔 후에 비교를 진행하는 방식이다.

1. 먼저 위와 같이 현재 Left ~ Right 범위에 있는 값들을 그대로 임시 배열에 옮겨준다.

2. 2개의 Index를 가르키는 값을 이용해서 왼쪽 배열과 오른쪽 배열의 값들을 비교하면서 원본 배열에 정렬시키면서 값을

   넣어준다.

   - 여기서 2개의 Index를 가르키는 값 이라고 했는데 갑자기 왠 2개의 Index를 가르키는 값일까?

   - 바로, 왼쪽 배열과 오른쪽 배열을 가르키는 것이다.

   - 즉, 왼쪽 배열은 왼쪽 배열의 범위만큼(Left ~ Mid) 가르킬 수 있는 값을 하나 만들고 오른쪽 배열은 오른쪽 배열의

     범위(Mid + 1, Right) 만큼 가르킬 수 있는 값을 하나 만드는 것이다.

   쉽게 이해하자면 다음의 그림과 같다.

빨강색이 현재 왼쪽 배열의 Index값, 파랑색이 오른쪽 배열의 Index값이다.

그리고 원본 배열에 저장하기 위한 Index 가 존재한다는 것도 헷갈리지말자.

즉, 우리는 왼쪽 배열의 Index를 가르키는 변수 하나, 오른쪽 배열의 Index를 가르키는 변수 하나, 이 값들의 비교를 통해서

다시 원본배열에 저장하기 위한 Index 하나. 총 3개가 필요하다 !

쉽게 표현하기 위해서 Left_Index, Right_Index로 두고, 임시 배열을 Temp[] 라고 두고 설명하겠다.

즉, Temp[Left_Index] 와 Temp[Right_Index]의 값을 비교해서 더 작은 값이 앞에 오도록 원본 배열에 저장해주는 것이다.

위와 같은 경우는 6 > 4 이므로, Temp[Right_Index] 값이 더 앞으로 와야 하는 상황이다.

이 때에는 원본Arr[Idx] = Temp[Right_Index] 가 되는 것이다.

반대의 경우라면, Arr[Idx] = Temp[Left_Index] 가 될 것이다. 이런식으로 1개씩 쪼개진 값을 2개씩 모두 합쳤다고 생각해보자.

즉, 배열은 다음과 같은 상태인 것이다.

이제부터 이 배열을 합쳐보도록 하자. 가장 먼저 [ 4 , 6 ] 과 [ 1, 7 ] 을 합쳐지는 과정을 해보도록 하자.

Left의 값은 0 , Right의 값은 3, Mid의 값은 1이 될 것이다.

즉, 왼쪽배열의 범위는 (0 ~ 1) 이 되고, 오른쪽배열의 범위는 (2 ~ 3)이 된다.

1. 먼저 Left ~ Right의 범위에 있는 값들을 임시 배열에 옮겨준다. 즉, 임시배열의 상태는 다음과 같아진다.

2. Left_Index와 Right_Index로 값을 비교하면서 원본 맵에 다시 합쳐준다.

   이 그림에서 빨강색은 Left_Index를 파랑색은 Right_Index를 의미한다.

   Temp[Left_Index]와 Temp[Right_Index]를 비교할 경우, Temp[Right_Index] 가 1로 더 작기 때문에

   Arr[Index] = Temp[Right_Index]가 되고 Right_Index는 ++가 된다.

   즉, 원본 배열의 상태와 Left_Index, Right_Index는 다음과 같아진다.

   즉, Right_Index는 ++가 되어 오른쪽 배열의 2번째 Index를 가르키고 있지만, Left_Index는 그대로 이다.

   또한, 원본 배열을 보면 처음에 [ 4, 6, 1, 7 ... ] 순서였는데, 가장 앞의 값이 바뀌면서 [ 1, 4, 1, 7 ] 이 된 형태이다.

   계속해서 Left_Index와 Right_Index를 비교해보자. 비교할 경우, 4 < 7 이기 때문에, Arr[Index ] = Temp[Left_Index]가 되고

   Left_Index는 ++가 되어 다음과 같아질 것이다.

   원본 배열에는 변화가 없는 것 처럼 보이지만, 1번 Index(2번째 값)에 '4'가 들어간 형태이다.

   이어서 비교를 하게 되면 6 < 7 이기 때문에, Arr[Index] = Temp[Left_Index]가 된다. 이후, Left_Index가 ++가 되면서

   비교가 끝나게 된다. 왜?? 왼쪽배열의 범위는 (Left ~ Mid)까지인데, 이 상황에서 Left = 0, Mid = 1이기 때문에

   Left_Index가 ++가 되면 2가 될 것이고 Mid값 보다 커지기 때문에 더 이상 비교를 그만하게 된다.

   즉, 아래와 같이 될 것이다.

   이런식으로 진행되는 것이 병합정렬인데, 우리가 여기서 해줘야할 과정이 한가지 더 있다.

    지금 위의 과정은 어떻게 보면 정렬이 완성된 형태이다. 하지만, 극단적으로 위의 상황을 한번 다음과 같이 바꿔보겠다.

    Left =0, Mid = 1, Right = 3인 경우이고, 밑에 배열은 원본 배열의 초기 상태이다.

    이 때, 정렬을 실행하면 어떻게 될까??

    아마, 4 > 1 이기 때문에, Arr[0] = 1, 그 다음 4 < 7 이기 때문에, Arr[1] = 4, 그 다음 100 > 7 이기 때문에

    Arr[2] = 7이 될 것이다. 이 경우에는 오른쪽 배열이 모든 범위에 대해서 비교를 다 끝냈기 때문에 더 이상 비교를 하지

    않을 것이다. 그렇다면, 원본 배열의 상태는 어떨까? 바로 다음과 같다.

    왜인지는 모르겠지만 100이라는 값이 제대로 들어가지지가 않았다. 왜 이런 현상이 발생하는 것일까??

    우리는 처음에 임시배열에 원본 배열의(Left ~ Right) 범위에 있는 값들을 옮겨주었다.

    그리고 왼쪽배열과 오른쪽 배열을 비교하는데, 비교를 그만두는 시점이 "왼쪽배열이 탐색 범위를 모두 탐색하거나,

    오른쪽배열이 탐색 범위를 모두 탐색하거나" 둘 중 하나만 만족하면 비교를 그만하는 것이었다.

    즉 ! 오른쪽 배열이 탐색 범위를 모두 탐색을 해서 비교를 그만하는 경우에 왼쪽 배열에는 더 큰 값이 남아 있음에도

    값이 제대로 들어가지지 않는 문제가 발생한다.

    따라서, 우리는 이 경우에 이 문제를 해결하기 위해서 임시 배열의 값을 다시 원본의 값으로 옮겨 주어야 한다.

    그렇다면, 우리는 왼쪽 배열이 덜 끝났는데, 오른쪽 배열이 탐색이 다 끝나서 종료되었다 ! 라는걸 어떻게 알 수 있을까??

    바로 Mid 값과 Left_Index값을 통해서 알 수 있다.

    왼쪽 배열의 범위는 Left ~ Mid 이다. 즉, 예를 들어서 Left값이 0이고 Mid 값이 1이라고 가정했을 때, 왼쪽배열이

    범위 내에 있는 모든 값들을 탐색을 다해서 종료되었다면 아마 Left_Index의 값이 ++가 됨에 따라 '2'까지 갔을 것이다.

    하지만, 오른쪽 배열이 탐색을 다해서 종료되었다면?? Left_Index의 값이 아무리 커봤자 Mid값일 것이다.

    즉, Left_Index의 값이 Mid값보다 작거나 같으면 왼쪽 배열이 탐색을 덜 했음에도 오른쪽 배열 때문에 종료되었음을

    의미하는 것이고, 위와 같은 문제점이 존재한다는 이야기이다.

   

    이런식으로 진행되는 것이 병합정렬이다. 코드를 보면서 깔끔하게 정리해보자.

void Merge(int Start, int Mid, int End)   
{
    for (int i = Start; i <= End; i++)        // 1. Start ~ End까지의 값들을 임시 배열에 옮겨주기.
    {
        Temp_Arr[i] = Arr[i];
    }
    int Left_Part = Start;                        // Left_Index값은 Start부터
    int Right_Part = Mid + 1;                 // Right_Index값은 Mid + 1부터
    int Idx = Start;                               // 원본 배열에 저장을 위한 Index는 Start부터.

    while (Left_Part <= Mid && Right_Part <= End)    // 왼쪽배열 or 오른쪽 배열 둘 중 한 배열의 탐색이 끝날때까지
    {
        if (Temp_Arr[Left_Part] <= Temp_Arr[Right_Part])    // 오른쪽 배열의 값이 더 크면
        {
            Arr[Idx] = Temp_Arr[Left_Part];    // 왼쪽 배열의 값을 저장해주고
            Left_Part++;                              // Left_Index값++
        }
        else                                             // 왼쪽 배열의 값이 더 크면
        {
            Arr[Idx] = Temp_Arr[Right_Part];  // 오른쪽 배열의 값을 저장해주고
            Right_Part++;                            // Right_Index값++
        }
        Idx++;                                            // 원본 Index++
    }

    if (Mid >= Left_Part)                            // 문제점이 발생하는 조건. 왼쪽배열이 덜 끝났을 때
    {
        for (int i = 0; i <= Mid - Left_Part; i++)
        {
            Arr[Idx + i] = Temp_Arr[Left_Part + i];    // 다시 원본의 맵에 그만큼 옮겨주는 과정 필요 !
        }
    }
}  

   

# 시간복잡도

- 먼저 퀵소팅과 비슷하게 Merge Sort는 반으로 나누는 과정이 필요하다. 즉, 퀵소팅의 이상적인 경우와 시간복잡도가

   동일하다.

   [ 퀵소팅 알아보기(Click) ]

   지금까지는 퀵소팅과 동일하니 설명을 더 하지는 않겠다. 일반적인 경우 병합정렬은 퀵소팅과 같이

   시간복잡도가 이 나오게 된다.

   그렇다면 최악의 경우를 알아보자.

   퀵소팅의 경우, 최악의 경우 Pivot을 잘못 선택할 경우 만큼의 시간복잡도를 가지게 됬다.

   하지만 Merge Sort의 경우?? 일단 Pivot을 선택하는 과정이 없다. 무조건 반씩 나누기 때문에 이런 최악의 경우가

   존재하질 않는다. 즉 MergeSort의 경우 퀵소팅과 달리 최악의 경우도 동일하게 의 시간복잡도를

   갖게 되는 것이다.

  

   그럼 무조건 Merge Sort가 더 좋겠네?? 라고 생각할 수 있지만 MergeSort의 가장 큰 단점이 하나 있다.

   바로 '임시적인 배열을 만들 추가적인 공간 필요' 이다. 위에서 우리는 임시 배열을 만들어서 그 배열에 값을 옮겨놓고

   비교하면서 다시 원본맵에 합치면서 정렬하는 식으로 구현하였다. 즉, 우리가 만들어야 할 임시배열이 필요하다는 것이고

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

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
int Temp_Arr[MAX];
bool Flag[10000];
 
void Print()
{
    cout << "##########################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << endl;
    cout << "##########################################################################################################" << endl;
    cout << endl;
}
 
void Merge(int Start, int Mid, int End)
{
    for (int i = Start; i <= End; i++)
    {
        Temp_Arr[i] = Arr[i];
    } 
    int Left_Part = Start;
    int Right_Part = Mid + 1;
    int Idx = Start;
 
    while (Left_Part <= Mid && Right_Part <= End)
    {
        if (Temp_Arr[Left_Part] <= Temp_Arr[Right_Part])
        {
            Arr[Idx] = Temp_Arr[Left_Part];
            Left_Part++;
        }
        else
        {
            Arr[Idx] = Temp_Arr[Right_Part];
            Right_Part++;
        }
        Idx++;
    }
 
    if (Mid >= Left_Part)
    {
        for (int i = 0; i <= Mid - Left_Part; i++)
        {
            Arr[Idx + i] = Temp_Arr[Left_Part + i];
        }
    }
}
 
void Merge_Sort(int Start, int End)
{
    if (Start < End)
    {
        int Mid = (Start + End) / 2;
        Merge_Sort(Start, Mid);
        Merge_Sort(Mid + 1, End);
        Merge(Start, Mid, End);
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < MAX; )
    {
        Arr[i] = rand() % 300 + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
    cout << "[ Initialize Array State ]" << endl;
    Print();
    Merge_Sort(0, MAX - 1);
    cout << "[ After Sorting Array State]" << endl;
    Print();
 
    return 0;
}