[알고리즘]분할정복을 이용한 정렬 알고리즘 - 병합 정렬 & 쾌속 정렬
[ 분할 정복 ]
분할 정복 (divide-and-conquer) 접근 방법은 주어진 문제의 규모가 클 때 문제를 작은 부분 문제로 나눠서 해결하는 방식입니다.
부분 문제로 나누는 작업을 반복하여 그 해답을 찾고, 다시 그 해답을 합쳐서 처음 문제에 대한 해답을 유도하는 것입니다.
- 분할 정복 알고리즘의 세 단계
1. 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 부분 문제로 나눕니다.
2. 정복(conquer) : 각 부분 문제에 대한 해답을 구합니다.
3. 결합(combine) : 각 부분 문제의 해답을 결합하여 전체 문제에 대한 해답을 구합니다.
일반적인 정렬 알고리즘(bubble sort, insertion sort, selection sort)은 한 쌍식 비교하여 정렬을 하기 때문에 O(N^2)이라는 시간 복잡도를 가지게 됩니다.
이보다 더 빠르게 정렬을 하기 위해 분할 정복을 사용하며, 분할 정복 알고리즘을 사용한 정렬 알고리즘이 바로 병합 정렬(merge sort)와 쾌속 정렬(quick sort)입니다.
[ 병합 정렬 Merge Sort ]
병합 정렬(merge sort)은 잘 알려진 정렬 알고리즘 중 하나이며, 많은 원소로 구성된 배열을 작은 크기의 부분집합으로 나누어 각각을 정렬하고 정렬된 부분집합을 오름차순 또는 내림차순을 유지하면서 합치는 방식입니다.
시간 복잡도는 O(N logN)입니다.
1. 분할(divide) : 배열을 더 이상 쪼개지지 않을때까지 절반으로 분할한다.
2. 정복(conquer) : 각 절반을 재귀적으로 정렬한다.
3. 결합(combine) : 정렬된 두 부분 배열을 병합한다.
void merge(int ls, int le, int rs, int re, int A[])
{
int lptr = ls, rptr = rs, bptr = 0;
int *B = (int*)calloc((le - ls) + (re - rs) + 2, sizeof(int));
while(lptr <= le && rptr <= re){
if(A[lptr] < A[rptr])
B[bptr++] = A[lptr++];
else
B[bptr++] = A[rptr++];
}
if(lptr > le)
for(int i = rptr; i <= re; i++)
B[bptr++] = A[i];
if(rptr > re)
for(int i = lptr; i <= le; i++)
B[bptr++] = A[i];
A <- B;
}
void merge_sort(int s, int e, int A[])
{
if(s == e)
return;
int m = (s + e) / 2;
merge_sort(s, m, A);
merge_sort(m + 1, e, A);
merge(s, m, m + 1, e, A);
}
[ 쾌속 정렬 Quick Sort ]
병합 정렬의 목적이 대용량의 데이터를 정렬하는 것이라면, 퀵 정렬(quick sort)는 평균 실행 시간을 줄이는 것이 목표입니다.
퀵 정렬은 주어진 배욜울 작은 크기의 부분 배열로 나누고, 각 부분 배열을 정렬 후, 병합합니다.
병합 정렬과 매우 유사해 보이지만, 퀵 정렬의 key point는 분할입니다.
피봇(pivot)이라는 원소 P를 기준으로 배열을 분할합니다. 왼쪽 부분 배열 L은 피봇 P 보다 작거나 같은 원소들의 집합이고, 오른쪽 부분 배열 R은 피봇 P 보다 큰 원소들의 집합입니다.
시간 복잡도는 O(N logN)입니다.
1. 분할(divide) : 피봇(pivot)을 기준으로 두 부분으로 분할한다.
2. 정복(conquer) : 재귀적으로 각 부분 배열을 L P R 순으로 정렬을 한다.
| 분할 전 | ||||||||
| 5 (pivot) |
6 | 7 | 3 | 1 | 9 | 2 | 4 | 8 |
| 분할 후 | ||||||||
| L | pivot | R | ||||||
| 4 | 2 | 3 | 1 | 5 | 9 | 7 | 6 | 8 |
int partition(int s, int e, int A[])
{
int pivot = A[s];
int left = s + 1;
int right = e;
while(left <= right){
while((A[right] >= pivot) && (left <= right))
right--;
while((A[left] <= pivot) && (left <= right))
left++;
if(left <= right)
swap(A[left], A[right]);
}
swap(A[right], A[s]);
return right;
}
void quick_sort(int s, int e, int A[])
{
if(s >= e)
return;
int m = partition(s, e, A);
quick_sort(s, m - 1, A);
quick_sort(m + 1, e, A);
}