문제 개요
원소들의 집합이 주어졌을 때, 어떤 순열(permutation)이 병합 정렬(Merge Sort)의 최악의 경우(worst case)를 만들어내는지 찾는 문제입니다. 병합 정렬은 점근적으로 항상 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]이 됩니다.
접근 방법
핵심 아이디어는 병합 정렬의 분할 과정을 역으로 시뮬레이션하는 것입니다. 정렬된 배열에서 시작해, 이후 병합 단계에서 두 정렬된 부분 배열 사이의 교차가 최대화되도록 원소를 재배치하면 모든 병합 단계에서 최대 비교 횟수(부분 배열 크기의 합 - 1)가 발생하게 됩니다. 이를 위해 다음 세 가지 함수를 정의합니다.
- merge(): 왼쪽 배열(left)과 오른쪽 배열(right)의 원소를 원래 배열(arr)에 순서대로 결합합니다.
- divide(): 배열에서 짝수 인덱스의 원소들은 left 배열로, 홀수 인덱스의 원소들은 right 배열로 분배합니다.
- gen_worst_seq(): 재귀적으로 배열을 분할하고 각 부분에 대해 같은 과정을 반복한 뒤 결과를 다시 결합하여 최악의 경우 순열을 생성합니다.
알고리즘 단계
- merge(arr, left, right, l_index, m_index, r_index): i를 0부터 m_index - l_index까지 증가시키며 arr[i] := left[i]를 수행하고, 이어서 j를 0부터 r_index - m_index - 1까지 증가시키며 arr[i + j] := right[j]를 수행합니다.
- divide(arr, left, right, l_index, m_index, r_index): i를 0부터 m_index - l_index까지 증가시키며 left[i] := arr[i * 2]를 수행하고, i를 0부터 r_index - m_index - 1까지 증가시키며 right[i] := arr[i * 2 + 1]을 수행합니다.
- gen_worst_seq(arr, l_index, r_index): l_index < r_index인 경우에만 다음을 수행합니다.
- m_index := l_index + (r_index - l_index) / 2 로 중간 지점을 계산합니다.
- 크기가 m_index - l_index + 1인 배열 left와 크기가 r_index - m_index인 배열 right를 선언합니다.
- divide()로 배열을 분할한 후, 왼쪽 구간과 오른쪽 구간에 대해 각각 gen_worst_seq()를 재귀 호출합니다.
- 마지막으로 merge()로 두 부분을 다시 결합합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
int i;
for (i = 0; i <= m_index - l_index; i++)
arr[i] = left[i];
for (int j = 0; j < r_index - m_index; j++)
arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
for (int i = 0; i <= m_index - l_index; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r_index - m_index; i++)
right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
if (l_index < r_index) {
int m_index = l_index + (r_index - l_index) / 2;
int left[m_index - l_index + 1];
int right[r_index - m_index];
divide(arr, left, right, l_index, m_index, r_index);
gen_worst_seq(left, l_index, m_index);
gen_worst_seq(right, m_index + 1, r_index);
merge(arr, left, right, l_index, m_index, r_index);
}
}
int main() {
int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
int n = sizeof(arr) / sizeof(arr[0]);
gen_worst_seq(arr, 0, n - 1);
display(arr, 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