개념
주어진 원소들의 집합이 있을 때, 이 원소들을 어떤 순서(순열)로 배치해야 병합 정렬(Merge Sort)의 최악의 경우(Worst Case)가 발생할까요?
병합 정렬은 점근적으로(asymptotically) 항상 O(n log n)의 시간 복잡도를 가지지만, 실제 실행 환경에서는 비교 연산 횟수가 많을수록 더 많은 시간이 소요됩니다. 따라서 우리가 구해야 하는 것은 일반적인 병합 정렬 알고리즘으로 정렬할 때 가장 많은 비교 횟수를 유발하는 입력 원소의 순열입니다.
예시
다음과 같이 정렬된 배열이 있다고 가정해 보겠습니다.
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
이 배열이 병합 정렬에서 최악의 성능을 보이도록 만드는 입력 배열은 다음과 같습니다.
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
접근 방법
그렇다면 주어진 입력 집합에 대해 병합 정렬의 최악의 경우를 만드는 입력은 어떻게 얻을 수 있을까요?
핵심 아이디어는 배열을 상향식(bottom-up)으로 구성하는 것입니다.
정렬된 배열이 {11, 12, 13, 14, 15, 16, 17, 18}이라고 해봅시다.
병합 정렬의 최악의 경우를 만들려면, 위 정렬된 배열을 만들어낸 병합(merge) 연산이 최대한 많은 비교를 수행해야 합니다. 이를 위해 병합 연산에 참여하는 왼쪽 부분 배열과 오른쪽 부분 배열에는 정렬된 배열의 원소들이 번갈아 가며 교차 배치되어야 합니다. 즉, 왼쪽 부분 배열은 {11, 13, 15, 17}, 오른쪽 부분 배열은 {12, 14, 16, 18}이 되어야 합니다.
이렇게 하면 배열의 모든 원소가 최소 한 번씩은 비교되므로 최대 비교 횟수가 발생합니다. 이제 동일한 논리를 왼쪽과 오른쪽 부분 배열에도 재귀적으로 적용합니다.
- 배열
{11, 13, 15, 17}의 최악의 경우는 왼쪽 부분 배열이{11, 15}, 오른쪽 부분 배열이{13, 17}일 때 발생합니다. - 배열
{12, 14, 16, 18}의 최악의 경우는 왼쪽 부분 배열이{12, 14}, 오른쪽 부분 배열이{16, 18}일 때 발생합니다.
전체 알고리즘
GenerateWorstCase(arr[])
- 두 개의 보조 배열(left, right)을 생성하고, 원본 배열의 원소들을 번갈아 나누어 저장합니다.
- 왼쪽 부분 배열에 대해 재귀 호출합니다 —
GenerateWorstCase(left) - 오른쪽 부분 배열에 대해 재귀 호출합니다 —
GenerateWorstCase(right) - 왼쪽과 오른쪽 부분 배열의 모든 원소를 다시 원본 배열로 복사합니다.
C 코드 예제
// 병합 정렬의 최악의 경우를 생성하는 C 프로그램
#include <stdlib.h>
#include <stdio.h>
// 배열을 출력하는 함수
void printArray(int A1[], int size1){
for (int i = 0; i < size1; i++)
printf("%d ", A1[i]);
printf("\n");
}
// 왼쪽과 오른쪽 부분 배열을 하나로 합치는 함수
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
int i; // 두 번째 반복문에서 사용
for (i = 0; i <= m1 - l1; i++)
arr1[i] = left1[i];
for (int j = 0; j < r1 - m1; j++)
arr1[i + j] = right1[j];
}
// 원소들을 왼쪽/오른쪽 부분 배열에
// 번갈아 저장하는 함수
int split(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
for (int i = 0; i <= m1 - l1; i++)
left1[i] = arr1[i * 2];
for (int i = 0; i < r1 - m1; i++)
right1[i] = arr1[i * 2 + 1];
}
// 병합 정렬의 최악의 경우를 생성하는 함수
int generateWorstCase(int arr1[], int l1, int r1){
if (l1 < r1){
int m1 = l1 + (r1 - l1) / 2;
// 두 개의 보조 배열 생성
int left1[m1 - l1 + 1];
int right1[r1 - m1];
// 원소들을 왼쪽/오른쪽 부분 배열에
// 번갈아 저장
split(arr1, left1, right1, l1, m1, r1);
// 전반부와 후반부에 대해 재귀 호출
generateWorstCase(left1, l1, m1);
generateWorstCase(right1, m1 + 1, r1);
// 왼쪽과 오른쪽 부분 배열을 다시 합침
join(arr1, left1, right1, l1, m1, r1);
}
}
// 드라이버 코드
int main(){
// 정렬된 배열 초기화
int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
printf("Sorted array is \n");
printArray(arr1, n1);
// 병합 정렬의 최악의 경우 생성
generateWorstCase(arr1, 0, n1 - 1);
printf("\nInput array that will result in " "worst case of merge sort is \n");
printArray(arr1, n1);
return 0;
}실행 결과
Sorted array is 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Input array that will result in worst case of merge sort is 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26