병합 정렬 그 두 번째 이야기(Merge Sort)

이번 포스트는 병합 정렬에 대한 두 번째 글입니다. 그러니 병합 정렬에 대해 잘 모르시는 분은 제가 저번에 적었던 글을 참고하셔도 됩니다.

2022.10.20 - [개념 정리/알고리즘] - 병합 정렬(Merge Sort)

병합 정렬 과정 다시 보기

병합 정렬을 간단하게 얘기하면 배열을 반씩 나누고 나눠진 배열들을 정렬시킨 후 정렬된 두 배열을 다시 하나의 배열로 합치는 정렬 알고리즘이었습니다. 이 과정을 Divide & Conquer의 시각에 맞춰서 보면 세 단계로 나눌 수 있었고 각각 Divide, Conquer, Combine(Merge)로 볼 수 있었습니다.

이번에는 병합 정렬 과정을 Top-down, Bottom-up 방식으로 나눠서 보겠습니다.

• Top-down: 하나의 커다란 문제를 여러 개의 작은 문제들로 나누어서 작은 문제들의 답을 찾는 과정
• Bottom-up: 가장 작은 문제에서 시작해서 작은 문제의 답들을 합쳐서 큰 문제의 답으로 찾는 과정

배열의 길이가 1이 될 때까지 절반씩 나누는 과정을 Top-down, 나눠진 배열들을 합치는 과정을 Bottom-up 과정이라 볼 수 있습니다. 여기서 basic operation이 일어나는 곳은 bottom-up 과정에서 일어납니다. 그러면 병합 정렬을 재귀 없이 Bottom-up 과정만 반복문을 이용해서 구현할 수 있을 것입니다.

 

아래의 그림은 merge sort 과정에서 나누는 부분은 생략하고 그린 그림입니다.

merge sort의 merge 과정

빨간색 테두리 안의 배열들은 길이가 1, 주황색 테두리 안에는 2, 노란색 테두리 안에는 4의 길이를 가진 배열들만 있습니다. 이러한 특징으로 인해 저번처럼 사이즈를 줄여가며 재귀를 들어가는 게 아니라 size라는 변수를 만들고 이를 2배씩 증가시키면서 반복문을 실행하게 할 수 있습니다. 반복문이 진행되는 동안 병합의 대상 배열들을 정하는 인덱스들도 정의할 수 있을 것입니다. 이러한 생각들을 C++ 코드로 구현하면 아래와 같습니다.

void mergeSortIter(int numArray[], int start, int end)
{
    int arrLength = end - start + 1;
    int size = 1;
    while (size < arrLength)
    {
        for (int i = 0; i < arrLength; i += 2 * size)
        {
            // low: 병합 대상인 왼쪽 배열의 인덱스, high: 병합 대상인 오른쪽 배열의 인덱스
            // mid: 병합 대상인 왼쪽 배열의 끝 인덱스
            // low ~ mid: 왼쪽 배열, mid + 1 ~ high: 오른쪽 배열
            int low = i;
            int mid = low + size - 1;
            int high = i + 2 * size - 1 >= arrLength ? arrLength - 1 : i + 2 * size - 1;

            // Merge
            int tmp[_MAX_LENGTH_] = {0};    // _MAX_LENGTH_ 는 입력으로 들어오는 배열의 길이와 같은 값이라 가정
            for (int j = low; j <= high; j++) { tmp[j] = numArray[j]; }    // 병합의 대상들만 복사

            int leftPtr, originPtr, rightPtr;
            leftPtr = originPtr = low;
            rightPtr = mid + 1;

            while (leftPtr <= mid && rightPtr <= high)
            {
                if (tmp[leftPtr] <= tmp[rightPtr]) { numArray[originPtr++] = tmp[leftPtr++];  }
                else { numArray[originPtr++] = tmp[rightPtr++]; }
            }
            while (leftPtr <= mid) { numArray[originPtr++] = tmp[leftPtr++]; }
            while (rightPtr <= high) { numArray[originPtr++] = tmp[rightPtr++]; }
        }

        size *= 2;
    }
}

코드를 보면 merge 과정은 저번의 merge sort 할 때의 merge 과정과 동일한 것을 볼 수 있습니다. 다시 한번 얘기하지만 여기서의 핵심은 재귀를 통해서 들어가는 Top-down 과정을 생략할 수 있다는 점입니다!