2017. 4. 29. 22:07
병합정렬(Merge Sort) 알고리즘-자료구조2017. 4. 29. 22:07
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| void merge(int *arr, int *sorted, int left, int mid, int right){ | |
| int L1 = left; | |
| int L2 = mid+1; | |
| int idx= left; | |
| while(L1 <= mid && L2 <= right){ | |
| if(arr[L1] <= arr[L2]) sorted[idx++]=arr[L1++]; | |
| else sorted[idx++]=arr[L2++]; | |
| } | |
| if(L1 > mid){ | |
| L1 = L2; | |
| mid = right; | |
| } | |
| while(L1 <= mid){ | |
| sorted[idx++] = arr[L1++]; | |
| } | |
| while(left <= right){ | |
| arr[left] = sorted[left++]; | |
| } | |
| } | |
| void divide(int *arr, int *sorted, int left, int right){ | |
| if(left >= right) return; | |
| int mid = (left + right) / 2; | |
| divide(arr, sorted, left, mid); | |
| divide(arr, sorted, mid+1, right); | |
| merge(arr, sorted, left, mid, right); | |
| } | |
| void MergeSort(int *arr, int left, int right){ | |
| int sorted[right+1]; | |
| divide(arr, sorted, left, right); | |
| } | |
| int main (){ | |
| int arr[] = {1, 9, 2, 6, 4, 0, 9}; | |
| MergeSort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1); | |
| for(int i=0; i<sizeof(arr)/sizeof(arr[0]); i++){ | |
| printf("%d ", arr[i]); | |
| } | |
| printf("\n"); | |
| return 0; | |
| } |
정렬 중 O(nlogn)의 시간복잡도를 가진 방법으로, 개인적으로는 퀵소트나 힙정렬 보다는 구현이 간단하다.
정렬해야하는 원소가 적다면(정확한 것은 모르겠지만 5개 이하) 삽입정렬이 더 낫다고도 한다.
스택오버플로우를 보면 퀵 정렬이 최악의 경우 O(n^2)임에도 여러가지 이유로
병합 정렬보다 나은 성능을 보인다고 하는데, 확인해보아야 할 듯 싶다.
C++ std library에는 퀵 정렬과 힙 정렬을 적당히(?) 활용한 Intro sort라는 게 쓰이는 듯 하다.
(http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort)
https://gist.github.com/woo972/0924604b96188cb78b9cf8b1a34fbd19
'알고리즘-자료구조' 카테고리의 다른 글
| SegmentTree(구간트리) (0) | 2017.02.19 |
|---|
