1. [CS] O(n log n) 정렬 - 분할 정복과 합병 정렬(Merge sort)

서론

분할 정복(Divide and conquer)은 커다란 문제를 작은 sub 문제로 나눈다음에 그것들을 다시 합쳐서 해결하는 개념이다. 

분할 정복 도식화

일반적인 분할정복의 시퀀스는 다음과 같다:

function solve(problem):
    if (problem is small enough): // base case
        return trivial solution
    else:
        divide problem into subproblems
        solve each subproblem recursively
        combine the results

 

1. Divide: 문제를 더 작게 쪼갠다.
2. Conquer: 하위 문제를 재귀적으로 해결한다.
3. Combine: 하위 문제의 답을 바탕으로 최종 결과를 얻는다.

분할 정복은 고등 수학을 배웠다면 누구나 알고있는 미분의 개념과 유사하고, 최초 개념은 고대 그리스로 거슬러 올라갈만큼 상당히 유서깊은 알고리즘이므로 따로 부연 설명이 필요없고 사용 예시(합병 정렬)을 보자.

합병 정렬 / 병합 정렬(Merge sort)

합병 정렬은 대표적인 $ O(n log n)$ 정렬 알고리즘 중 하나로, 분할 정복의 가장 대표적인 예이다. 합병 정렬의 도식화를 보면 분할 정복의 도식화를 그대로 빼다박은걸 알 수 있다.

(좌) 분할 정복 도식화, (우) 합병 정렬 도식화

따라서 구현 자체는 Basic하다.

1. Divide : 문제를 더 작게 쪼갠다. -> 정렬 해야할 배열을 절반으로 쪼갠다.
2. Conqure : 하위 문제를 재귀적으로 해결한다. -> 쪼개진 배열을 재귀적으로 정렬하여 해결한다.
3. Combine: 하위 문제의 답을 바탕으로 최종 결과를 얻는다.  -> 정렬된 배열을 병합하여 최종 결과를 얻는다.

void MergeSort(vector<int>& arr, int left, int right)
{
	if (left >= right)return;
	int mid = (left + right) / 2;
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	Merge(arr, left, mid, right);
}

합병(Merge) 과정

 

합병 정렬 진행 순서(from namuwiki)

합병 정렬에는 쪼개고 쪼갠 배열의 합병 결과를 저장해야 할 임시 배열이 필요하기 때문에 정렬을 해야할 배열의 크기만큼 메모리가 더 필요하다.

1. 두 배열 병합  

왼쪽과 오른쪽 배열을 각각 비교하면서 작은 값을 먼저 sorted에 복사

for (; i <= mid && j <= right; k++) {
	if (arr[i] <= arr[j]) sorted[k] = arr[i++];
	else sorted[k] = arr[j++];
}

2. 잔여 요소 복사

둘 중 하나의 배열이 먼저 끝났을 경우 나머지 배열의 남은 값들을 그대로 sorted에 복사

if (i > mid) {
	for (int l = j; l <= right; l++, k++)
		sorted[k] = arr[l];
} else {
	for (int l = i; l <= mid; l++, k++)
		sorted[k] = arr[l];
}

 

3. 정렬 결과 원본 배열로 복사

임시 배열 sorted에 저장해둔 정렬 결과를 다시 arr로 복사

 

for (int l = left; l <= right; l++)
	arr[l] = sorted[l];

 

전체 코드

vector<int> sorted;

void Merge(vector<int>& arr, int left, int mid, int right)
{
	int i = left, j = mid + 1, k = left;
	for (; i <= mid && j <= right; k++)
	{
		if (arr[i] <= arr[j]) sorted[k] = arr[i++];
		else sorted[k] = arr[j++];
	}

	if (i > mid)
	{
		for (int l = j; l <= right; l++, k++)
		{
			sorted[k] = arr[l];
		}
	}
	else
	{
		for (int l = i; l <= mid; l++, k++)
		{
			sorted[k] = arr[l];
		}
	}

	for (int l = left; l <= right; l++)
	{
		arr[l] = sorted[l];
	}
}