Programming/Algorithm
머지소트(merge sort)
J_____
2021. 6. 16. 22:03
반응형
Merge sort은 'divide and conquer(분할정복)'의 대표적인 알고리즘이다.
분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.
(출처: https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 빠른 정렬이나 합
ko.wikipedia.org
merge sort는 다음 3가지 단계로 동작한다.
분할(Divide): 입력 배열을 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병(merge)한다.
1. 분할
2.정복 & 결합
코드로 구현해 보면 다음과 같다.
#include <stdio.h>
int arr[8] = { 1, 3, 2, 7, 8, 5, 6, 4};
int temp[8];
void merge_sort(int start, int end)
{
int mid = (start + end) / 2;
if (start >= end)
return;
merge_sort(start, mid);
merge_sort(mid + 1, end);
int a = start;
int b = mid + 1;
int c = 0;
while (1) {
if (a == mid + 1 && b == end + 1)
break;
if (a == mid + 1)
temp[c++] = arr[b++];
else if (b == end + 1)
temp[c++] = arr[a++];
else if (arr[a] < arr[b])
temp[c++] = arr[a++];
else
temp[c++] = arr[b++];
}
for(int i = 0; i < c; i++)
arr[start + i] = temp[i];
}
void print()
{
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
print();
merge_sort(0, 7);
print();
return 0;
}
반응형