[3. Quick sort, 쾌속 정렬]
● 방식
→ 집합 A의 원소들을 오름차순으로 정렬하고자 할 때(또는 내림차순)
→ 집합 내의 원소 중 하나를 무작위로 골라 (주로 A[0]=pivot)
→ pivot을 기준으로 pivot보다 작은 원소는 pivot의 앞에
→ pivot보다 큰 원소는 pivot의 뒤에 배치한다.
→ 이 때, pivot을 제외한 맨 앞과 맨 뒤의 값들을 서로 비교하여
→ 앞의 값이 뒤의 값보다 클 경우, 자리를 서로 바꾼다.
→ 배열을 두 개로 분할한다는 점에서 합병정렬과 비슷하지만, 결합하지 않으므로 합병정렬의 발전형이라 할 수 있다.
● 알고리즘
→ Divide : m=Partition()
→ Conquer : Quick_sort(s, m-1, A), Quick_sort(m+1, e, A)
→ Degenerate case : 원소가 한 개인 경우 (s>=e)
● 구현
#include <stdio.h>
void swap(int* A, int* B) {
int temp;
temp = *A;
*A = *B;
*B = temp;
}
int Partition(int s, int e, int A[]) {
int pivot = A[s], lptr = s + 1, rptr = e;
while (lptr <= rptr) {
while ((A[rptr] >=pivot) && (lptr<=rptr))
rptr--;
while ((A[lptr] <= pivot) && (lptr<=rptr))
lptr++;
if (lptr <= rptr) {
swap(&A[lptr], &A[rptr]);
/*
printf("정렬과정 : ");
for (int i = 0; i < 8; i++) {
printf("%d ", A[i]);
}
printf("\n");
*/
}
swap(&A[rptr], &A[s]);
/*
printf("정렬과정 : ");
for (int i = 0; i < 8; i++) {
printf("%d ", A[i]);
}
*/
printf("\n");
return rptr;
}
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);
}
int main() {
int N, A[100];
scanf_s("%d", &N);
for (int i = 0; i < N; i++)
scanf_s("%d", &A[i]);
int s = 0, e = N - 1;
Quick_sort(s, e, A);
for (int i = 0; i < N; i++)
printf("%d, ", A[i]);
}
● 성능
→ 최선의 경우 : T(n) = 2*T(n) + O(n) = O(nlogn)
→ 평균의 경우 : T(n) = (1/n)*∑{T(k-1)+T(n-k)}+O(n) = O(nlogn)
→ 최악의 경우 : T(n) = T(n-1) + O(n) = O(n²)
→ 즉, 퀵정렬은 다른 알고리즘에 비해 빠른 편이지만 운이 나쁘면 (Ex. 정렬하고자 하는 순서의 반대 순서로 정렬되어 있는 배열을 만날 경우) 오히려 수행 시간이 나빠질 수 있다.
※ 참고로, 정렬 과정은 아래와 같습니다.
최선의 경우 :
평균의 경우 :
최악의 경우 :
'알고리즘 > Divide & Conquer' 카테고리의 다른 글
[알고리즘] Divide & Conquer (2) - Merge sort (0) | 2022.11.08 |
---|---|
[알고리즘] Divide & Conquer (1) - Binary search (2) | 2022.11.05 |