합병 정렬 (Merge Sort)

합병 정렬(Merge Sort)란?

데이터들을 최소 단위로 쪼개고, 합치면서 정렬하는 방식이다.

합병 정렬의 특징

시간복잡도 O(nlog₂n)

 

분할정복 알고리즘이다.

배열을 분리한 뒤, 합칠 때 새로운 배열이 필요하다.

합병 정렬 원리

원래의 배열을 하나의 데이터를 가지는 배열로 쪼갠 뒤, 합치면서 정렬한다.

아래 그림은 합치면서 정렬하는 과정이다.

 

1. 정렬할 데이터를 담을 배열을 만든다. (변수명은 mergeArr로 했음)

1. 왼쪽 배열과 오른쪽 배열을 비교하면서 mergeArr에 추가한다.
2. 하나의 배열이 끝이나면, 다른 배열에 남은 값들을 mergeArr에 추가한다.
3. 정렬된 배열(mergeArr)을 원래의 배열에 복사한다.

와 ppt로 내가 이해했던 걸 그리는 게 보통 일이 아니군...

합병 정렬 구현 (C++)

#include <iostream>
#include <ctime>

void Merge(int* arr, int left, int middle, int right)
{
    // 정렬할 데이터를 담을 새로운 배열
    int mergeArr[100];
    int mergeIndex = 0;

    // 나눴을 때, 
    int aIndex = left; // 왼쪽 배열 start index
    int bIndex = middle + 1; // 오른쪽 배열 start index

    // 왼쪽 배열이 끝나거나, 오른쪽 배열이 끝날 때까지
    while (aIndex <= middle && bIndex <= right) 
    {
        // 정렬하여 새로운 배열에 담아줌.
        if (arr[aIndex] < arr[bIndex]) 
        {
            mergeArr[mergeIndex] = arr[aIndex];
            mergeIndex++;
            aIndex++;
        }
        else
        {
            mergeArr[mergeIndex] = arr[bIndex];
            mergeIndex++;
            bIndex++;
        }
    }

    // 왼쪽 배열에 데이터 값이 남아있으면,
    while (aIndex <= middle)
    {
        // 새로운 배열에 담아줌.
        mergeArr[mergeIndex] = arr[aIndex];
        mergeIndex++;
        aIndex++;
    }
    // 오른쪽 배열에 데이터 값이 남아있으면,
    while (bIndex <= right)
    {
        // 새로운 배열에 담아줌.
        mergeArr[mergeIndex] = arr[bIndex];
        mergeIndex++;
        bIndex++;
    }

    mergeIndex--;
    // 정렬된 배열을 원래 배열에 복사한다.
    while (mergeIndex >= 0)
    {
        arr[left + mergeIndex] = mergeArr[mergeIndex];
        mergeIndex--;
    }
}
void MergeSort(int* arr, int left, int right)
{
    // 배열 크기가 하나보다 작으면 더 이상 배열을 나누지 않는다.
    if (left >= right) 
    {
        return;
    }
    
    int middle = (left + right) / 2; // left right 값을 이용해 중간 값을 계산
    
    // 배열을 나눌 수 있을 때까지 나눈다.
    MergeSort(arr, left, middle); // 왼쪽 배열
    MergeSort(arr, middle + 1, right); // 오른쪽 배열

    // 나눠진 배열들을 정렬하며 합친다.
    Merge(arr, left, middle, right);
}

int main()
{
    std::cout << "----------Random Value Array----------\n";
    srand((unsigned int) time(0));
    int arr[10];
    int arrLength = 10;
    for (int i = 0; i < arrLength; i++)
    {
        arr[i] = rand() % 100;
        std::cout << arr[i] << " ";
    }

    std::cout << "\n----------Merge Sort----------\n";
    MergeSort(arr, 0, arrLength - 1);
    for (int i = 0; i < arrLength; i++)
    {
        std::cout << arr[i] << " ";
    }
}

출력

----------Random Value Array----------
38 19 38 37 55 97 65 85 50 12
----------Merge Sort----------
12 19 37 38 38 50 55 65 85 97