[알고리즘] Merge Sort 병합정렬
*병합정렬
'분할 정복'을 이용한 정렬 방법이다.
큰 문제를 작은 문제로 나누어서(분할:divide) 풀어가는(정복:conquer) 과정이다.
*병합정렬을 사용하는 이유
선택, 버블, 삽입정렬이 있지만 병합정렬을 사용하면 O(nlogn)만에 정렬을 할 수 있다.
즉, 성능이 좋다.
[복습: malloc 함수]
병합정렬을 배우기 전에 c언어의 동적할당에 대해서 복습해보자.
malloc함수: void형 포인터로 동적으로 공간을 할당해주는 함수이다.
전역, 지역변수와 달리 사용자가 원하는 시점에서 생성하고 소멸이 가능하다.
|
왜 void형 포인터일까? 예를 들어서, void *ptr = malloc(sizeof(int)); 위 문장은 결국 void *ptr = malloc(4); 와 같다. 즉, 공간의 크기는 함수가 알 수 있지만 이게 어떤 자료형을 의미하는 지 알 수 없다. 컴퓨터가 자료형을 알기 위해서는 int *ptr = (int*)malloc(sizeof(int)); 로 int형인 것을 알려줘야한다. |
병합정렬에 대해서 분할 그리고 정복 순서대로 알아보자!
1.분할(divide)
우선 주어진 배열을 분할해줘야 한다.
예를 들어서 그림을 그려보자.
위의 그림에서 보이듯이 우선은 데이터가 하나씩 구분이 될 때까지 진행을 한다.
이때, "둘로 나눠주며" 하나씩 구분이 되게하자.
|
왜 하나씩 구분이 될 때까지 둘로 나누며 구분을 하는 걸까? 처음부터 하나씩 구분을 해버리면 더 간단할 수 있지만, 재귀적으로 구현하기 위하여 둘로 나눠준다.
참고(재귀적 방법을 사용하지 않고 병합정렬 구현하기) |
재귀적인 구현이 힘들다.
이를 코드로 나타내자.
mid변수의 역할: mid변수를 중심으로 배열을 둘로 나눠줄 수 있다.
예를 들어서, left = 0, right = 9 라하자.
그럼 mid는 4이므로 0 ~ 4의 배열 그리고 5 ~ 9의 배열로 나눠줄 수 있다.
(추가 설명. 0 ~ 4 배열 = left ~ mid 배열 그리고 5 ~ 9 배열 = mid + 1 ~ right 배열)
그럼 18행과 19행이 이해가 간다.
다시 MergeSort로 0 ~ 4배열이 들어가고 그게 다시 0 ~ 2배열 그리고 3 ~ 4 배열로 나뉜다.
또 여기서 0 ~ 2 배열은 0 ~ 1 배열 그리고 2 ~ 2 배열로 나뉜다.
.
.
.
계속 순환적으로 반복되어 밑과 같은 그림이된다.
left와 right가 같아지는 순간이 base case가 된다.
여기서부터는 정복에 대해 알아보자!
2.정복(conquer)
분할된 배열을 다시 결합하여 정복하자
들어가기에 앞서서 기본적인 방법을 소개하겠다.
밑의 그림을 순서대로 살펴보자.
1.
배열 A,B,C가 있다.
배열 A와 B는 오름차순으로 정렬된 상태이다.
(오름차순 1, 2, 3, 4 .. 점점 커지는 상태)
2.
배열 A,B에 있는 숫자들을 배열 C로 오름차순으로 옮기고자 한다.
A의 첫번째 숫자 1 vs B의 첫번째 숫자 2
1이 더 작으므로 1을 이동시킨다.
3.
B의 첫번째 숫자 2 vs A의 두번째 숫자 3
2가 더 작으므로 2를 이동시킨다.
4.
A의 두번째 숫자 3 vs B의 2번째 숫자
3이 더 작으므로 3 이동
5.
위와 마찬가지로 나머지를 순서대로 반복하다보면
배열 C에는 "123457"의 순서로 정렬된다.
이 방식을 "고대로" 결합과정에 사용할 것이다.
위의 그림으로 나타낸 과정을 밑 사진속에 코드를 설명하면서 활용하였다.
위의 그림에서 A,B,C배열을 생각하면서 주석과 함께 읽으면 이해가 될 것이다.
3.Code
|
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 |
#include <stdio.h> #include <stdlib.h>
void MergeTwoArea(int arr[], int left, int mid, int right) {
int l_idx = left; //앞 배열의 첫번째 첨자번호, 그림에서 A배열의 역할 int r_idx = mid + 1; //뒷 배열의 첫번째 첨자번호, 그림에서 B배열의 역할 int i;
int *sortArr = (int *)malloc(sizeof(int) * (right + 1)); //결합이될 배열,그림에서 C배열을 동적으로 할당해준다. int s_idx = left; //두 배열을 합해서 옮겨질 배열의 첫번째 첨자번호, 그림에서 C배열의 역할
while(l_idx <= mid && r_idx <= right) { //아까 그림에서 서로 비교하는 과정과 같다. 순서 2 ~ 5번의 과정이다. if(arr[l_idx] <= arr[r_idx]){ //앞 배열(그림에서 A배열)의 원소가 더 작다면~ sortArr[s_idx] = arr[l_idx]; l_idx++; }else{ //뒷 배열(그림에서 B배열)의 원소가 더 작다면~ sortArr[s_idx] = arr[r_idx]; r_idx++; }
s_idx++; //A,B,C배열의 첨자들이 각각 다르게 증가한다는 것을 잊지말자. }
if(l_idx > mid) //이 과정까지 A배열은 C배열로 모두 옮겨졌는데 만약, B배열에는 원소가 남아있다면~ { for(i = r_idx; i <= right; i++) sortArr[s_idx++] = arr[i]; } else //이 과정까지 B배열은 C배열로 모두 옮겨졌는데 만약, A배열에는 원소가 남아있다면~ { for(i = l_idx; i <= mid; i++) sortArr[s_idx++] = arr[i]; }
for(i = left; i <= right; i++) //할당된 배열에 옮겼으므로 모든 원소를 원래 배열로 옮겨주자. arr[i] = sortArr[i];
free(sortArr); }
void MergeSort(int arr[], int left, int right){ int mid;
if(left < right){ mid = (left + right) / 2;
MergeSort(arr, left, mid); MergeSort(arr, mid + 1, right);
MergeTwoArea(arr, left, mid, right); } }
int main(int argc, const char * argv[]) { int arr[7] = {3,2,4,1,7,6,5}; int i;
MergeSort(arr,0,sizeof(arr) / sizeof(int) - 1);
for(i = 0; i < 7; i++) printf("%d ",arr[i]);
printf("\n");
return 0; } |
cs |
4. 성능평가
O(nlogn)
장점: 성능이 좋다.
단점: 임시메모리가 필요하다는 단점이 있다.
연결리스트를 사용할 경우에는 더 좋은 성능을 기대할 수 있다.