3. 병합 정렬 merge sort

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 

5
5
4
3
2
1

예제 출력 

1
2
3
4
5

1. 병합 정렬 merge sort 소개

앞선 두 개의 정렬 알고리즘은 어찌됐건 O(n ^ 2)의 시간복잡도를 가진다.

위의 문제를 보면 최악의 경우 백만 칸의 배열을 정렬해야 한다.

백만의 제곱으로는 시간 제한내에 들어오지 못한다.

그러면 더 빠른 알고리즘을 알아햐 하니까, 병합 정렬에 대해 알아보려고 한다.

우선 병합 정렬은 분할 정복이다. 즉 문제를 쪼개어서 부분 문제로 만들어 해결하자는 뜻으로, 결국 재귀적인 패러다임이다.

때문에 하위 문제는 상위 문제보다 적용 범위가 작아야 하고, 범위가 작아지는 한계인 탈출지점이 있어야 한다.

분할 정복은 다음 세 부분으로 나눌 수 있다.

1) 분할 : 원래의 문제를 분할하여 같은 문제 유형의 더 작은 하위 문제들로 나눈다.

2) 정복 : 하위 문제들을 재귀적으로 해결해야 한다. 충분히 하위 문제가 작아졌다면 탈출해야 한다.

3) 합치기 : 하위 문제들의 답을 합쳐 원래 문제를 해결한다.

도식화 하자면 다음과 같다.

이제 병합 정렬을 분할 정복해보자. 하위 문제를 잘 정의해야 한다.

당연히 원래의 문제는 수열을 정렬하는 것이다. 하위 문제는 수열의 일부분만 정렬하는 문제라고 정의하자.

폰 노이만은 병합 정렬을 만들 때 다음의 단계를 거치라고 했다.

1) 분할 : 수열을 반으로 쪼갠다.  [14, 7, 3, 12, 9, 11, 6, 2] ->  [14, 7, 3, 12] /  [9, 11, 6, 2]

2) 정복 : 쪼개진 수열 각각에 대해 정렬한다. [3, 7, 12, 14] /  [2, 6, 9, 11]

3) 결합 : 두 수열을 합쳐서 정렬한다 [2, 3, 6, 7, 9, 11, 12, 14]

하위 배열 [14, 7, 3, 12]은 어떻게 정렬할까? 마찬가지로 분할-정복-결합을 거쳐 [3, 7, 12, 14] 로 만든다.

다음은 위의 예시가 어떻게 재귀적으로 전개되는지 과정을 보여준다.

2. 코드

#include <stdio.h>
#include <vector>
using namespace std;
 
int n, tmp;
vector<int> v;
 
void mergesort(int from, int to);
void merge(int from, int mid, int to);
 
void mergesort(int from, int to) {
    if (from == to) {
        return;
    }
 
    int mid = (from + to) / 2;
    mergesort(from, mid);
    mergesort(mid + 1, to);
 
    merge(from, mid, to);
}
 
void merge(int from, int mid, int to) {
    int l = from, r = mid + 1;
    int len = to - from + 1;
    vector<int> tmp(len);
 
    for (int i = 0; i < len; ++i) {
        if (l > mid)
            tmp[i] = v[r++];
        else if (r > to)
            tmp[i] = v[l++];
        else if (v[l] < v[r])
            tmp[i] = v[r++];
        else
            tmp[i] = v[l++];
    }
 
    for (int i = 0; i < len; ++i)
        v[from + i] = tmp[i];
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    mergesort(0, n - 1);
 
    for (int i = 0; i < n; ++i)
        printf("%d ", v[i]);
 
    return 0;
}

아마 병합단계를 구성하는게 가장 어려웠을 것이다.

단순히 두 배열을 합치고 지금까지 배운 삽입-정렬이나 거품-정렬을 쓸 수도 있지만

그리한다면 오히려 더 느린 알고리즘이 되어버린다.

이를 선형시간에 해결할 아이디어는, 우리가 문제를 재귀적으로 풀고 있었다는 점에서 떠올릴 수 있다.

우리가 합쳐서 정렬할 두 부분 배열의 특징은 무엇인가? 바로 이미 재귀적으로 정렬되어버린 배열이라는 점이다.

따라서 다음과 같은 방법을 쓸 수 있다.

4칸 부분 배열 두 개를 합쳐 8칸 짜리 배열을 만들어야 한다고 해보자.

첫칸에는 어떤 숫자가 와야 하는가? 8개 숫자 중에 가장 작은 수이다.(오름차순)

고맙게도 두 부분 배열의 맨 앞은 가장 작은 숫자의 두 후보이다. 따라서 두 배열의 맨 앞의 숫자 중에 작은 수를 가져다 쓰면 된다.

둘째 칸에는 어떤 숫자가 와야 하는가? 두번째로 작은 숫자이다.

후보는 두 배열의 맨 앞 숫자이다.(인덱스로는 1 / 0)이다. 두 숫자중 작은 수를 가져다 쓴다.

....

그래서 n칸 짜리 임시배열을 만들고, 채우고, 다시 원본 배열에 복사해주는 편이 편하다.

원본 배열만 써서 이를 구현하면(in-place) 번거롭고, 오래걸린다.

3. 시간 복잡도

결론적으로 병합-정렬의 시간복잡도는 O(n * log n)이다. 백만 개가 주어진다면, O(백만 * 6)이다.

어떻게 차수는 줄어들 수 있었을까? 재귀적으로 분석해보자.

결국 최종적으로 완성되는 배열은 두 부분 배열(이미 정렬된)을 합치면서 완성된다. 위에서 합치는 방법이 선형시간임을 보였으므로,

합치는데는 O(n)이다.

그러면 정렬된 두 부분배열을 만드는데는 얼마나 걸렸을까? 각각의 크기는 n/2 이므로 O(2 * (n / 2)) = O(n) 만큼 걸렸다.

그림으로 알아보자.

그림을 통해 알 수 있는 사실은 O(n)은 트리의 높이만큼 수행된다는 것이다.

트리의 높이는 얼마나 되는가? log n 이다. 따라서 시간복잡도는 O(n * log n)이다.

또한 생각할 점은 원래의 배열이 어찌되었건 간에 쪼개는 상황은 반복된다는 것이다.

따라서 최선의 경우(이미 정렬되어 있어도)에도 시간복잡도는 O(n * log n) 이다.