병합정렬
2019. 10. 31. 15:17ㆍ알고리즘/암기
분할정복의 대표적인 예
merge : 정복, sort : 분할, 2개의 함수로 구성되어 있다
1. stable sort 중 하나로 중복 키 순서가 보장된다
2. 평균, 최악, 최고의 시간복잡도는 동일하게 O(NlgN)이다
3. 임시로 저장해야하는 배열이 있어야하므로 기존보다 2배의 메모리를 잡아먹는다
위 채점은 merge sort로 아래 채점은 heap sort이다
깃허브주소: https://github.com/surinoel/boj/blob/master/merge_sort.cpp
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 <cstdio> | |
int a[1000000]; | |
int b[1000000]; | |
void merge(int start, int end) { | |
int mid = (start + end) / 2; | |
int i = start; | |
int j = mid + 1; | |
int k = 0; | |
while (i <= mid && j <= end) { | |
if (a[i] <= a[j]) { | |
b[k++] = a[i++]; | |
} | |
else { | |
b[k++] = a[j++]; | |
} | |
} | |
while (i <= mid) { | |
b[k++] = a[i++]; | |
} | |
while (j <= end) { | |
b[k++] = a[j++]; | |
} | |
for (int i = start; i <= end; i++) { | |
a[i] = b[i - start]; | |
} | |
} | |
void sort(int start, int end) { | |
if (start == end) { | |
return; | |
} | |
int mid = (start + end) / 2; | |
sort(start, mid); | |
sort(mid + 1, end); | |
merge(start, end); | |
} | |
int main(void) { | |
int n; | |
scanf("%d", &n); | |
for (int i = 0; i < n; i++) { | |
scanf("%d", &a[i]); | |
} | |
sort(0, n - 1); | |
for (int i = 0; i < n; i++) { | |
printf("%d\n", a[i]); | |
} | |
return 0; | |
} |
'알고리즘 > 암기' 카테고리의 다른 글
11^n 이항정리로 구하기 (0) | 2019.11.16 |
---|---|
점 3개의 방향 알아내기 CCW, CW (0) | 2019.10.31 |
재귀의 장단점 (0) | 2019.10.30 |
세그먼트 트리 (0) | 2019.10.30 |
set 컨테이너 (0) | 2019.10.23 |