합병 정렬 (Merge sort)

분할정복법과 합병 정렬 (Merge sort)

합병 정렬은 앞서 알아본 선택, 삽입, 버블 정렬과는 다르게 분할정복법이라는 개념을 사용합니다.

분할정복법(Divide-And-Conquer)이라는 것은 주어진 문제를 다음과 같은 3단계의 절차를 통해 해결하는 방법입니다.

  1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다.
  2. 정복 : 각각의 작은 문제를 순환적으로 해결한다.
  3. 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구한다.

그럼 이를 토대로 합병 정렬의 과정을 살펴보겠습니다.

합병 정렬은 여러 개의 데이터를 한 번에 정렬하는 것이 아닌 이를 계속해서 반으로 나눈 후 다시 합병하는 과정에서 정렬이 이루어집니다.

분할을 반복하다보면 마지막은 길이가 1인 구간으로 나뉘어집니다. 더이상 분할이 불가능할때 다시 합병하면서 정렬을 하는것입니다. 그렇기 때문에 합병 정렬에서 가장 중요한 부분은 실제 정렬을 수행하는 합병(merge)하는 과정입니다.

그럼 합병과정에서 정렬은 어떻게 이루어질까요? 다음 그림을 통해서 실제 정렬이 이루어지는 합병 과정을 좀 더 자세히 알아보겠습니다.

먼저 위 그림은 합병이 이루어 지기 위한 이미 정렬된 2개의 블록이 존재하는 모습입니다. 현재 두개의 블록은 이미 길이가 1인 구간으로 나눠진 배열부터 시작해 각각 합병 과정을 거쳐 정렬된 상태로 만들어진 배열입니다.
이 두개의 블록을 정렬된 상태를 유지하며 합치기 위해서는 i 인덱스에 있는 값과, j 인덱스에 있는 값을 하나씩 비교한 후 추가배열에 저장하면 됩니다.

위 그림처럼 하나의 블록이 모두 합쳐 졌을 경우 나머지 블록은 순서대로 배열에 저장하면 됩니다.

모든 합병을 마친 후 이 추가배열의 값으로 기존 배열의 해당 구간에 복사하면 됩니다.

합병 정렬 의사 코드

의사 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
mergeSort(A[],p,r){
if(p<r) then{
q <- (p+r)/2;
mergeSort(A,p,q);
mergeSort(A,q+1,r);
merge(A, p, q, r);
}
}

merge(A[], p, q, r){
정렬되어 있는 ㅜ 배열 A[p..q]와 A[q+1...r]을 합하여
정렬된 하나의 배열 A[p...r]을 만든다.
}

합병 정렬 c++ 코드

이제 의사 코드를 바탕으로 c++ 코드를 작성하면 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>

#define ITEM_SIZE 10

using namespace std;

void print_arr(int a[], int size) {
for (int i = 0; i < size; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}

void merge(int a[], int left, int mid, int right) {
int i, j, k;

i = left;
j = mid + 1;
k = left;

int tmp_arr[ITEM_SIZE];

// left 부터 mid 까지의 블록과 mid + 1 부터 right 까지의 블록을 서로 비교
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
tmp_arr[k] = a[i];
i++;
}
else {
tmp_arr[k] = a[j];
j++;
}
k++;
}

// left 블록의 값이 다 처리되었지만, right 블록의 index가 남아 있는 경우
// right 블록의 남은 부분을 순차적으로 tmp_arr에 복사
if (i > mid) {
for (int m = j; m <= right; m++) {
tmp_arr[k] = a[m];
k++;
}
}
// left 블록의 남은 부분을 순차적으로 tmp_arr에 복사
else {
for (int m = i; m <= mid; m++) {
tmp_arr[k] = a[m];
k++;
}
}

// 임시 배열인 tmp_arr의 값을 원본 배열에 복사한다.
for (int m = left; m <= right; m++) {
a[m] = tmp_arr[m];
}
}

void merge_sort(int a[], int left, int right) {
int mid;

if (left < right) {
// 절반으로 나누기 위해 중간 위치 찾기
mid = (left + right) / 2;

// 분할
merge_sort(a, left, mid);
merge_sort(a, mid + 1, right);

// 합병
merge(a, left, mid, right);
}
}

int main() {
int a[ITEM_SIZE] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
print_arr(a, ITEM_SIZE);
merge_sort(a, 0, ITEM_SIZE - 1);
print_arr(a, ITEM_SIZE);
return 0;
}

합병 정렬 시간 복잡도

이제 마지막으로 합병 정렬의 시간 복잡도를 알아보겠습니다. 데이터가 n개 일때 합병 정렬로 계산하는 시간을 T(n)이라고 하겠습니다.
정렬을 위해서 반으로 분할한 후 n/2개의 블럭에 재귀함수를 호출하면, 반으로 분할된 블럭 2개에 대한 정렬을 수행해야하므로 T(n/2) + T(n/2)의 시간이 걸립니다. 두개의 정렬된 블럭을 merge할 때 두 블럭을 한번씩 비교하므로 merge 시간은 n입니다.
따라서, merge sort의 시간 복잡도는 T(n) = T(n/2) + T(n/2) + n이 됩니다.

결국 분할을 반복하면 위와 같은 그림의 식을 도출할 수 있고, 이 식을 수학적으로 풀어보면 O(nlogn)이 됩니다.

합병 정렬과 퀵 정렬 비교

아직 퀵 정렬에 대해 다루지 않았지만 합병 정렬과 퀵 정렬 모두 시간 복잡도로 O(nlogn)을 갖습니다. 그러나 퀵 정렬과 합병 정렬에는 서로 다른 특징이 있습니다.

합병 정렬은 합병 과정에서 임시적인 저장공간으로 데이터를 담고 있는 배열과 같은 크기인 추가 배열을 사용하기 때문에 추가적인 메모리가 필요합니다. 그러나 퀵 정렬은 추가 메모리를 사용하지 않고 내부 교환만으로 수행되는 차이가 있습니다.

또한 합병 정렬은 어떤 상황이라도 항상 O(nlogn)의 시간 복잡도를 갖지만 퀵 정렬의 경우 아이러니하게도 정렬하기 위해 정렬이 되어 있는 데이터를 사용할 경우 O(n^2)의 시간복잡도를 갖게 됩니다. (이 경우는 다음에 퀵 정렬에 대해 포스팅하며 알아보겠습니다.) 그러나 최악의 경우가 아닐 경우 일반적으로 퀵 정렬이 합병 정렬에 비해 빠른 성능을 보입니다.

합병 정렬은 퀵 정렬보다 성능이 전반적으로 떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 stable sort라는 점입니다. 퀵 정렬의 경우 만약 배열 A[25] = 100, A[33] = 100 인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있습니다. 그에 반해서 합병 정렬은 이전의 순서를 유지하면서 정렬된 상태를 만들 수 있습니다.

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님

댓글

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×