퀵 정렬(Quicksort)은 리스트를 두 부분으로 나누는 방식으로 동작하는 정렬 기법입니다. 먼저 분할(partition) 알고리즘을 통해 피벗(pivot) 요소를 하나 선택합니다. 피벗을 기준으로 왼쪽 부분에는 피벗보다 작은 값들이, 오른쪽 부분에는 피벗보다 큰 값들이 배치됩니다. 분할이 완료되면 나누어진 각 리스트에 대해 동일한 절차를 재귀적으로 반복 적용합니다.
이 글에서 다루는 구현의 특징은 피벗 요소를 무작위(랜덤)로 선택한다는 점입니다. 피벗을 무작위로 고르면 이미 정렬된 배열이나 역순 배열처럼 고정 피벗 방식에서 최악의 성능(O(n2))이 나오기 쉬운 입력에서도 평균적으로 좋은 성능을 기대할 수 있습니다. 피벗을 선택한 뒤 분할을 수행하고, 배열을 재귀적으로 정렬합니다.
퀵 정렬 기법의 복잡도
시간 복잡도 — 최선의 경우와 평균적인 경우 O(n log n), 최악의 경우 O(n2)
공간 복잡도 — O(log n)
입력 — 정렬되지 않은 리스트: 90 45 22 11 22 50
출력 — 정렬 후 배열: 11 22 22 45 50 90
알고리즘
partition(array, lower, upper)
입력 — 데이터 배열, 하한 경계, 상한 경계
출력 — 올바른 위치에 배치된 피벗
Begin
index := lower
pivot := higher
for i in range lower to higher, do
if array[i] < array[pivot], then
exchange the values of array[i] and array[index]
index := index + 1
done
exchange the values of array[pivot] and array[index]
End
random_pivot_partition(array, lower, upper)
입력 — 데이터 배열, 하한 경계, 상한 경계
출력 — 무작위로 선택한 피벗의 최종 인덱스
Begin
n := a random number
pvt := lower + n mod (upper – lower + 1)
exchange the values of array[pvt] and array[upper]
index := Partition(array, lower, upper)
return index
End
quickSort(array, left, right)
입력 — 데이터 배열과 배열의 하한·상한 경계
출력 — 정렬된 배열
Begin
if lower < right then
q = random_pivot_partition(array, left, right)
quickSort(array, left, q-1)
quickSort(array, q+1, right)
End
예제 코드
#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) {
// 배열 요소를 무작위 위치로 섞는 함수
srand(time(NULL));
for (int i = MAX - 1; i > 0; i--) {
int j = rand()%(i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 마지막 요소(high)를 피벗 값으로 삼아 배열을 분할하는 함수
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
// 피벗의 최종 인덱스를 찾는 과정
if(a[i] < a[pivot]) {
swap(a[i], a[index]);
index++;
}
}
swap(a[pivot], a[index]);
return index;
}
int RandomPivotPartition(int a[], int low, int high){
// 피벗을 무작위로 선택
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1); // 부분 배열에서 피벗 위치를 무작위로 결정
swap(a[high], a[pvt]);
return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
// 리스트를 재귀적으로 정렬
int pindex;
if(p < q) {
pindex = RandomPivotPartition(arr, p, q); // 피벗을 무작위로 선택
// 퀵 정렬을 재귀적으로 수행
quick_sort(arr, p, pindex-1);
quick_sort(arr, pindex+1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX; i++)
arr[i] = i + 1;
random_shuffle(arr); // 배열을 무작위로 섞기
quick_sort(arr, 0, MAX - 1); // 배열의 요소들을 정렬
for (i = 0; i < MAX; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
실행 결과
1부터 100까지의 숫자로 채운 배열을 무작위로 섞은 뒤 퀵 정렬로 정렬하면 다음과 같이 오름차순으로 출력됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
이처럼 무작위 피벗 선택 방식은 입력 데이터의 초기 순서에 따른 성능 편차를 줄여주므로, 실무에서도 퀵 정렬을 안정적으로 활용하기 위한 대표적인 기법 중 하나입니다.