알고리즘_8_병합 정렬(Merge Sort)
Aug 8, 2021
»
writing
K 실전 알고리즘 강좌(Algorithm Programming Tutorial) 동빈나 님 수업을 참고하여 작성하였습니다
8_병합 정렬(Merge Sort)
병합 정렬(Merge Sort)
1. 병합 정렬(Merge Sort) : 분할 정복 방법을 채택한 알고리즘 : 퀵 정렬과 동일한 시간 복잡도 가짐 : 퀵 정렬은 피벗 값에 따라 편향되게 분할됨 : 병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 N*logN 보장 : 피벗 값이 없고 항상 반으로 나눈다 : 이 단계의 크기가 logN이 되도록 만들어줌 : 합치는 순간에 정렬 수행하기 : 너비가 N번, 높이가 logN
일단 반으로 나누고 나중에 합쳐서 정렬하면 어떨까?
#include <stdio.h>
int number = 8;
int sorted[8]; // 정렬 배열은 반드시 전역변수로 선언
void merge(int a[], int m, int middle, int n) {
int i = m;
int j = middle + 1;
int k = m;
// 작은 순서대로 배열에 삽입
while (i <= middle && j <= n) {
if (a[i] <= a[j]) {
sorted[k] = a[i];
i++;
}
else {
sorted[k] = a[j];
j ++;
}
k++;
}
// 남은 데이터 삽입
if (i > middle) {
for (int t =j; t<=n;t++) {
sorted[k] = a[t];
k++;
}
} else {
for (int t = i; t <= middle; t++) {
sorted[k] = a[t];
k++;
}
}
// 정렬된 배열 삽입
for (int t =m; t <=n; t++) {
a[t] = sorted[t];
}
}
void mergeSort(int a[], int m, int n) {
// 크기가 1 보다 클 경우
if (m <n) {
int middle = (m + n) /2;
mergeSort(a, m, middle);
mergeSort(a, middle +1, n);
merge(a, m ,middle, n);
}
}
int main(void) {
int array[number] = {7,6,5,8,3,5,9,1};
mergeSort(array, 0, number-1);
for (int i=0; i <= number; i ++) {
printf("%d ", array[i]);
}
}
// 1 3 5 5 6 7 8 9