퀵정렬 기본 개념
퀵정렬은 병합정렬과 유사한 개념으로 선행 작업을 한 다음 재귀적으로 작은 문제를 해결하며 정렬하는 방법이다.
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체를 정렬시키는 방식을 이용한다.
정리하면 퀵정렬은 다음과 같은 과정으로 정렬을 진행한다.
- 주어진 배열에서 하나의 요소를 선택하고 이를 pivot으로 사용한다.
- 배열 내부의 모든 값을 검사하면서 pivot보다 작은 값들은 pivot을 기준으로 왼쪽에, 큰 값들은 오른쪽에 배치한다.
- 이 과정을 통해 배열을 두 부분으로 나눌 수 있다.
- 이렇게 나누어진 두 배열에서 또 다시 새로운 pivot을 만들고 두 개의 배열로 나누어준다.
- 더이상 배열을 나눌 수 없을 때까지 위 과정을 반복한다.
이렇게 퀵정렬은 분할 정복의 원리를 이용해 정렬을 수행한다. pivot을 중심으로 문제를 분할하고 이를 기준으로 작은 값과 큰 값을 나열하는 과정(정복)을 거친 뒤 모든 결과를 결합하여 전체의 큰 문제를 해결한다.
pivot 선정의 중요성
pivot을 선정하는 것은 퀵정렬에서 가장 핵심이 되는 요소이다. pivot에 따라 퀵정렬의 성능이 달라진다고 할 수 있다.
퀵정렬의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 O(N^2)으로 버블 정렬과 성능이 똑같아지게 된다. pivot에 따라 시간복잡도가 차이나는 이유는 pivot을 통해 나누는 배열의 위치 때문이다.
예를들어 배열이 pivot에 의해 매번 1개의 원소와 나머지 원소로 나누어진다면 n번의 분할이 필요하고 n-1번 비교하는 연산이 필요하기 때문에 시간 복잡도는 n*n-O(N^2)이 된다.
하지만 배열이 pivot에 의해 절반으로 유사하게 나뉘어진다면 n번의 분할이 필요하고 한 번의 분할이 수행될때마다 비교하는 데이터의 수가 절반으로 줄어들기 때문에 logn의 시간복잡도를 갖는다. 따라서 이러한 경우에는 O(nlogn)의 시간복잡도를 갖게된다.
그렇다면 pivot을 어떻게 선정하는 것이 좋을까? 일반적으로 정렬을 수행하기 위한 데이터의 내부 요소는 어떻게 배치되었는지 알지 못한채로 정렬을 수행하는 경우가 대부분이다. 따라서 아무리 최악의 경우가 일어날 수 있는 확률이 적다고 해도 pivot을 잘 선정해서 최악의 경우를 피해주어야한다.
pivot을 선택하는 방법은 대표적으로 3가지가 있다.
- 첫번째 값이나 마지막 값을 pivot으로 선정한다.
- 첫번째, 가운데, 마지막 값 중 중간 값을 pivot으로 선정한다. (Median of Three)
- 무작위 값을 pivot으로 선정한다.
이 3가지 방법 중 Median of Three를 사용하면 배열의 분할이 거의 이등분으로 유지가 될 가능성이 높기 때문에 이 방법이 가장 좋은 pivot 선정법이라고 할 수 있다.
예제
다음 배열을 퀵정렬로 정렬해보자.
구현
#include <stdio.h>
int partition (int arr[], int p, int r){
int low, high;
int pivot = arr[p]; // pivot 값 설정
low = p + 1; // low 는 pivot의 바로 다음 위치에서부터
high = r; // high는 전달된 끝지점
while(low <= high){
while(arr[low] < pivot) low++; // pivot 보다 작은 값이 나올때마다 이동
while(arr[high] > pivot) high--; // pivot 보다 큰 값이 나올때마다 이동
if (low <= high){ // low와 high 가 중단된 지점이 서로 위치가 역전된 지점이 아니라면
int temp = arr[low]; // low 와 high 의 값 변경
arr[low] = arr[high];
arr[high] = temp;
}
}
// 피벗과 high 위치 교환
int temp = arr[p];
arr[p] = arr[high];
arr[high] = temp;
return high; // 피벗 위치 반환
}
void quick_sort(int arr[], int left, int right){
if (left < right){
int pivot = partition(arr, left, right);
quick_sort(arr, left, pivot-1); // 피벗을 기준으로 왼쪽 배열 정렬
quick_sort(arr, pivot+1, right); // 피벗 기준으로 오른쪽 배열 정렬
}
}
int main (){
int arr [] = {3, 2, 1, 5, 7, 9, 6};
quick_sort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);
for (int i = 0 ; i < sizeof(arr)/sizeof(arr[0]) ; i++){
printf("%d ", arr[i]);
}
}