병합정렬

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

#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;
}
view raw mergesort.c hosted with ❤ by GitHub

'알고리즘 > 암기' 카테고리의 다른 글

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