1. 개요
퀵 정렬은 이름에서 알 수 있듯 굉장히 빠른 정렬이다. 퀵 정렬의 핵심은 피벗(pivot)이다.피벗을 통해서 재귀적으로 함수를 만들면 데이터를 빠르게 정렬한다. 병합 정렬과 마찬가지로 분할 정복(divide and conquer) 방법을 통해 작동한다.
2. 어떻게 움직이나?
퀵 정렬의 핵심은 분할 정복과 재귀, 피벗이다. 분할 정복과 재귀는 병합 정렬에서 했던 것과 비슷하다. 피벗은 우리 말로 축인데, 축보다 작은 건 왼쪽으로 보내고 큰 건 오른쪽으로 보내서 정렬하는 과정을 재귀적으로 되풀이하면 정렬이 끝난다. 번호를 붙여서 퀵 정렬 순서를 알아보자. 우선 정렬해야 할 정수배열 arr이 있다고 하자.1. arr에서 정렬해야 할 범위의 양 끝 번호를 left, right라고 하자. QuickSort함수에 인자로 arr, left, right을 넘겨준다.
2. 피벗은 left로 정한다.
3. 피벗보다 하나 오른쪽의 값부터 끝까지를 정렬한다. 이건 Partition 함수를 이용.
4. Partition 함수는 다음과 같이 동작한다. 일단 피벗보다 하나 오른쪽 값을 low로, 마지막 값을 high로 정한다.
5. Partition 함수 안에서 low와 high를 비교해서 high가 더 우선순위 상 앞에 와야 하면 low와 high를 바꾼다.
5-1. 만약 low의 우선순위가 피벗의 우선순위보다 위이면 low를 한 칸 오른쪽으로 이동시킨다.
5-2. 만약 low의 우선순위가
5-3. low가 high 보다 커지면 left와 high를 바꾸고 high를 리턴한다.
6. 피벗을 기준으로 두 개의 파티션이 생겼는데, 각각의 파티션에 대해 다시 재귀적으로 QuickSort를 호출한다.
7. 병합 정렬과는 달리 배열 내부에서 교환이 계속 일어나기 때문에 병합 필요 없고 정렬 끝.
3. 퀵 정렬의 C 소스코드
아래의 C로 짠 퀵 정렬의 코드를 보자.
#include <stdio.h>
#include <stdlib.h>
void Swap(int arr[], int idx1, int idx2){
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
int Partition(int arr[], int left, int right){
int pivot = arr[left];
int low = left+1;
int high = right;
while(low <= high){
while(pivot >= arr[low] && low <= right){
low++;
}
while(pivot <= arr[high] && high >= left+1){
high--;
}
if(low <= high){
Swap(arr, low, high);
}
}
Swap(arr, left, high);
return high;
}
void QuickSort(int arr[], int left, int right){
if(left <= right){
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot-1);
QuickSort(arr, pivot+1, right);
}
}
int main(void){
int arr[20];
int i;
for(i=0; i<20; i++){
arr[i] = rand() % 100 + 1;
}
printf("정렬 전 상태 : ");
for(i=0; i<20; i++){
printf("%d ",arr[i]);
} printf("\n");
QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);
printf("정렬 후 상태 : ");
for(i=0; i<20; i++){
printf("%d ", arr[i]);
} printf("\n");
return 0;
}
| cs |
4. 퀵 정렬의 시간복잡도
퀵 정렬의 시간복잡도는 \(O(n\log _2n)\) 으로 알려져 있다. 사실 피벗을 개떡같이 정하는 최악의 경우 시간복잡도는 \(O(n^2)\)지만, 퀵 정렬은 보통 최악의 경우를 고려하지 않는다. 보통은 피벗을 중간에 가깝게 설정함으로써 최선의 경우에 가까운 성능을 보인다고 한다. 또한 퀵 정렬은 병합 정렬과는 다르게 추가 메모리가 필요 없고, 컴퓨터 아키텍쳐를 효율적으로 활용하도록 설계되어서 다른 \(O(n\log n)\) 정렬 알고리즘들보다 더 좋은 성능을 기대할 수 있다.참고
윤성우.(2012).열혈 자료구조.오렌지미디어
댓글 없음:
댓글 쓰기