병합 정렬(Merge Sort)
개yo
앞선 포스팅에서는 앞도적으로 빠른 속도를 자랑하는 퀵 정렬에 대해 알아보았다. 하지만 이런 퀵 정렬 또한 최악의 상황 (거의 정렬이 되어있는 데이터)에서의 시간복잡도가 O(N * log N)을 보장하지 못한다는 단점을 가지고 있었다. 이런 단점을 보완하여 어떠한 경우에도 시간복잡도O(N * log N)을 보장하는 알고리즘이 있는데 그것이 바로 이번 포스팅에서 알아볼 병합정렬(Merge Sort)이다.
문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라
[ 6, 4, 3 ]
SOL
문제를 해결하기 위해 퀵정렬을 쓴다면 “일단 반으로 나누고 나중에 합쳐서 정렬하기” 를 생각해 볼 수 있다.
위와 같은 방식을 병합정렬 이라고 한다.
특징
- 어떠한 상황이든 시간 복잡도는 O(N * log N)을 보장한다.
- 분할, 정복 방법을 채택한 알고리즘이다.
구현
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
#include<iostream>
#define MAX 3
using namespace std;
// 정렬공간
int sorted[MAX];
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int arr[], int left, int mid, int right)
{
int i = left; // left list first index
int j = mid+1; // right list first index
int k = left; // sorted list first index
int l;
//왼쪽에서 정렬된 배열과 오른쪽에서 정렬된 배열을 합침
//둘중 하나가 끝까지 올때 까지 합침
while (i <= mid && j <= right)
{
if(arr[i] <= arr[j]) sorted[k++] = arr[i++]; // L[4 6] R[3]
else sorted[k++] = arr[j++]; // sorted[3]
}
// 6 4 비교 후 sorted에 저장
// sorted [4] 그럼 나머지 [6]은??? 아래에서 처리된다.
if(i > mid)// right list
for(l=j; l <= right; l++)
sorted[k++] = arr[l];
// 남아 있는 값들을 일괄 복사
// 이건 left list의 남은 짬들의 복사
else
for(l=i; l<=mid; l++)
sorted[k++] = arr[l]; // sorted[3, 4] sorted[3, 4, 6]
// sorted [4 6]
// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
for(l=left; l<=right; l++)
arr[l] = sorted[l];
// left[6 4] ~> left[4 6]
}
void MergeSort(int arr[], int left, int right)
{
int mid;
if(left < right)
{
mid = (left + right)/2;
// left list conquer [6 4]
MergeSort(arr, left, mid);
// right list conquer 대기 [3]
MergeSort(arr, mid+1, right);
// left & right combine L[6] R[4]먼저 삽입 후 L[4 6] R[3] 삽입
merge(arr, left, mid, right);
}
}
int main()
{
int n = MAX;
int list[n] = {6, 4, 3};
MergeSort(list, 0, n-1);
for(auto el : list)
cout << el << " ";
cout << endl;
}
출력
1
3 4 6
해설
위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.
- 크기가 1인 개별 배열로 나눈다.(재귀적 호출 이용)
- L_1 [6, 4] R_1[3]
- L_2[6] R_2[4]
1 2 3 4 5 6 7 8 9 10 11 12 13 14
void MergeSort(int arr[], int left, int right) { int mid; if(left < right) { mid = (left + right)/2; // left list conquer [6 4] MergeSort(arr, left, mid); // right list conquer 대기 [3] MergeSort(arr, mid+1, right); // left & right combine L[6] R[4]먼저 삽입 후 L[4 6] R[3] 삽입 merge(arr, left, mid, right); } }
크기가 1인 개별배열로 나누어 지면 스택마냥 두 리스트들을 정복(정렬)한다.
또는 정렬된 두 배열의 크기를 비교후 삽입한다.
- L_2[6] , R_2[4] 크기 비교 후 sorted[4] 에 삽입… L_2[6] 이 남게됨
1 2 3 4 5 6 7 8 9
//왼쪽에서 정렬된 배열과 오른쪽에서 정렬된 배열을 합침 //둘중 하나가 끝까지 올때 까지 합침 while (i <= mid && j <= right) { if(arr[i] <= arr[j]) sorted[k++] = arr[i++]; // L[4 6] R[3] else sorted[k++] = arr[j++]; // sorted[3] }
두 배열의 크기를 비교하고 남은 리스트의 요소를 sorted에 삽입한다.
1 2 3 4 5 6 7 8 9 10 11
// 6 4 비교 후 sorted에 저장 // sorted [4] 그럼 나머지 [6]은??? 아래에서 처리된다. if(i > mid)// right list for(l=j; l <= right; l++) sorted[k++] = arr[l]; // 남아 있는 값들을 일괄 복사 // 이건 left list의 남은 짬들의 복사 else for(l=i; l<=mid; l++) sorted[k++] = arr[l]; // sorted[3, 4] sorted[3, 4, 6]
- sorted에 삽입된 값을 두 배열에 합친 값 안에 넣어 초기화 시켜준다.
- sorted arr : 4 6
- before arr : 6 4
- after arr : 4 6
1 2 3 4 5
// sorted [4 6] // 배열 sorted[](임시 배열)의 리스트를 배열 arr[]로 재복사 for(l=left; l<=right; l++) arr[l] = sorted[l]; // left[6 4] ~> left[4 6]
- 정렬된 배열값을 대기중이던 배열과 함께 다시 실행된다.
- L_1 [6, 4] R_1[3] ~> L_1 [4, 6] R_1[3]
- arr[4, 6, 3]
1 2 3 4 5 6 7 8 9 10 11 12 13 14
void MergeSort(int arr[], int left, int right) { int mid; if(left < right) { mid = (left + right)/2; // left list conquer [6 4] MergeSort(arr, left, mid); // right list conquer 대기 [3] MergeSort(arr, mid+1, right); // left & right combine L[6] R[4]먼저 삽입 후 L[4 6] R[3] 삽입 merge(arr, left, mid, right); } }
마무리
이해하기 쉽도록 6 4 3의 3개의 요소를 가진 배열로 설명하지만 어떤 데이터든 위 과정의 반복이라고 생각하면 될것 같다.
추가적으로
병합정렬은 임시 배열을 전역 변수로 사용하는 이유는 메모리 자원의 낭비를 막기 위해서다. 메모리 낭비가 되는 이유는 만약 전역 변수가 아닌 함수 안에서 배열을 사용한다면 매번 배열이 선언됨으로 심각한 메모리 낭비가 발생하기 때문이다.이후 포스팅에서 설명할
힙 정렬은 이 메모리의 비효율성을 해결해 준다.