퀵 정렬(Quick Sort)은 분할 정복(Divide-and-Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 평균 시간 복잡도는 O(n·log n)으로 매우 효율적이지만, 피벗 선택이 운 나쁘게 이루어질 경우 최악의 경우 O(n²)까지 성능이 저하될 수 있습니다.
이러한 최악의 경우 발생 가능성을 줄이기 위해, 이 글에서는 랜덤화(Randomization)를 적용한 퀵 정렬을 C++로 구현하는 방법을 소개합니다. 피벗을 무작위로 선택하면 이미 정렬된 배열과 같은 편향된 입력에서도 균형 잡힌 분할을 기대할 수 있습니다.
알고리즘 개요
1. Partition(int a[], int l, int h)
배열의 마지막 요소를 피벗으로 삼아, 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 분할합니다.
Begin
pivot = h
index = l
for i = l to h-1 do
if a[i] < a[pivot] then
swap a[i] with a[index]
index = index + 1
done
done
swap a[pivot] with a[index]
return index
End
2. RandomPivotPartition(int a[], int l, int h)
난수를 생성하여 피벗 위치를 무작위로 결정한 뒤, 해당 요소를 배열 끝과 교환하고 일반 Partition 함수를 호출합니다.
Begin
n = rand()
pivot = l + n % (h - l + 1)
swap a[h] with a[pivot]
return Partition(a, l, h)
End
3. QuickSort(int a[], int l, int h)
재귀적으로 분할된 각 부분 배열에 대해 같은 과정을 반복 수행합니다.
Begin
if l < h then
pindex = RandomPivotPartition(a, l, h)
QuickSort(a, l, pindex - 1)
QuickSort(a, pindex + 1, h)
return 0
End
C++ 전체 예제 코드
#include <iostream>
#include <cstdlib>
using namespace std;
// 두 값을 교환하는 함수
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// 피벗을 기준으로 배열을 분할하는 함수
int Partition(int a[], int l, int h) {
int pivot, index, i;
index = l;
pivot = h;
for(i = l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
// 피벗을 무작위로 선택하는 함수
int RandomPivotPartition(int a[], int l, int h) {
int pvt, n, temp;
n = rand();
pvt = l + n % (h - l + 1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
// 재귀적으로 정렬을 수행하는 함수
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = RandomPivotPartition(a, l, h);
QuickSort(a, l, pindex - 1);
QuickSort(a, pindex + 1, h);
}
return 0;
}
int main() {
int n, i;
cout << "\n정렬할 데이터 개수를 입력하세요: ";
cin >> n;
int arr[n];
for(i = 0; i < n; i++) {
cout << "요소 " << i + 1 << " 입력: ";
cin >> arr[i];
}
QuickSort(arr, 0, n - 1);
cout << "\n정렬된 데이터: ";
for(i = 0; i < n; i++)
cout << "->" << arr[i];
return 0;
}
실행 결과
정렬할 데이터 개수를 입력하세요: 4
요소 1 입력: 3
요소 2 입력: 4
요소 3 입력: 7
요소 4 입력: 6
정렬된 데이터: ->3->4->6->7
핵심 포인트 정리
- 시간 복잡도: 평균 O(n·log n), 최악 O(n²) — 랜덤화를 통해 최악의 경우 발생 확률을 크게 낮출 수 있습니다.
- 공간 복잡도: 제자리(in-place) 정렬로 추가 메모리가 거의 필요하지 않습니다(O(log n) 재귀 스택).
- 랜덤 피벗의 장점: 이미 정렬되어 있거나 역순으로 정렬된 입력에서도 안정적인 성능을 보장합니다.