퀵 정렬(Quick Sort)이란?
퀵 정렬은 비교 연산을 기반으로 정렬되지 않은 리스트(배열)를 정렬하는 대표적인 정렬 기법으로, '파티션 교환 정렬(partition exchange sort)'이라고도 불립니다.
퀵 정렬은 불안정 정렬(unstable sort)에 속합니다. 즉, 값이 같은 요소들의 상대적인 순서가 정렬 후에도 유지되지 않습니다. 다만 배열 위에서 추가 메모리를 아주 적게 사용하면서 정렬을 수행할 수 있다는 큰 장점이 있습니다. 선택 정렬(selection sort)과 매우 유사하지만 항상 최악의 파티션을 선택하지는 않는다는 점에서, 선택 정렬보다 한 단계 발전된 형태라고 볼 수 있습니다.
퀵 정렬은 가장 효율적인 정렬 알고리즘 중 하나로, 배열을 더 작은 배열들로 분할하는 방식에 기반합니다. 이름 그대로 일반적인 정렬 알고리즘보다 훨씬 빠른 속도로 데이터를 정렬할 수 있으며, 병합 정렬(Merge Sort)과 마찬가지로 '분할 정복(divide and conquer)' 문제 해결 방법론에 속합니다.
퀵 정렬의 동작 방식
비유를 통해 쉽게 이해해 보겠습니다. 학생 이름이 적힌 종이들을 이름순으로 정렬해야 하는 상황을 가정해 봅시다. 다음과 같은 접근 방식을 사용할 수 있습니다.
피벗(Pivot) 선택 — 분할 기준이 될 임의의 값(예: L)을 하나 정합니다. 이 기준값을 피벗이라고 부릅니다.
두 그룹으로 나누기 — 종이 더미를 A~L과 M~Z 두 묶음으로 나눕니다. 두 묶음의 크기가 반드시 같을 필요는 없습니다.
반복 분할 — A~L 묶음과 M~Z 묶음 각각에 대해 같은 과정을 반복합니다. 묶음이 충분히 작아져 쉽게 정렬할 수 있을 때까지 계속 진행합니다.
병합 — 마지막에는 작은 묶음들을 순서대로 쌓아 올려 완전히 정렬된 명단을 완성합니다.
여기서 핵심은 분할할 때마다 재귀(recursion)를 활용해 단일 요소 배열에 도달할 때까지 같은 방식을 반복 적용한다는 점입니다. 이러한 특징 때문에 퀵 정렬은 '파티션 교환 정렬'이라고도 불립니다.
입력: arr[] = {7,4,2,6,3,1,5}
출력: 1 2 3 4 5 6 7동작 과정 상세 설명
개념을 확실히 이해하기 위해 예제를 살펴보겠습니다. 다음 배열을 정렬한다고 가정합니다.
50, 23, 9, 18, 61, 32
1단계 — 목록에서 피벗으로 사용할 값을 정합니다(일반적으로 마지막 값). 첫 번째 인덱스와 마지막 인덱스에 해당하는 "low"와 "high"가 있다고 가정합니다.
이 예제에서 low는 0, high는 5입니다. low와 high 위치의 값은 각각 50과 32이며, 피벗 값은 32입니다.
이제 파티션을 호출하여 피벗(32)이 제자리에 오도록 배열을 재배치합니다. 피벗 왼쪽에는 피벗보다 작은 요소들이, 오른쪽에는 피벗보다 큰 요소들이 위치하게 됩니다.
파티션 과정에서는 첫 번째 요소부터 시작해 피벗과 비교합니다. 50은 32보다 크므로 변경 없이 다음 요소 23으로 넘어갑니다.
23을 다시 피벗과 비교하면 23은 32보다 작으므로 50과 23을 교환합니다. 배열은 23, 50, 9, 18, 61, 32가 됩니다.
다음 요소 9 역시 피벗(32)보다 작으므로 50과 교환하면 배열은 다음과 같아집니다.
23, 9, 50, 18, 61, 32
마찬가지로 다음 요소 18도 32보다 작으므로 교환하면 배열은 다음과 같습니다.
23, 9, 18, 50, 61, 32 — 이제 61은 피벗(32)보다 크므로 변경하지 않습니다.
마지막으로 피벗인 32와 50을 교환하여 피벗을 올바른 위치로 옮깁니다.
이렇게 하면 피벗(32)이 실제 위치에 놓이게 되고, 왼쪽의 모든 요소는 피벗보다 작으며, 오른쪽의 모든 요소는 피벗보다 커집니다.
2단계 — 첫 번째 단계가 끝난 후 배열은 다음과 같습니다.
23, 9, 18, 32, 61, 50 (피벗: 32)
3단계 — 이제 리스트는 두 부분으로 나뉩니다.
- 피벗 앞쪽 부분 리스트: 23, 9, 18
- 피벗 뒤쪽 부분 리스트: 61, 50
4단계 — 각 부분 리스트에 대해 같은 과정을 재귀적으로 반복합니다.
최종 배열은 9, 18, 23, 32, 50, 61이 됩니다.
C++ 구현 예제
다음은 무작위 피벗(random pivot) 방식을 사용한 퀵 정렬의 C++ 구현 코드입니다.
#include <stdio.h>
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
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;
n = rand();
pvt = low + n % (high - low + 1);
swap(&a[high], &a[pvt]);
return Partition(a, low, high);
}
void QuickSort(int a[], int low, int high) {
int pindex;
if (low < high) {
pindex = RandomPivotPartition(a, low, high);
QuickSort(a, low, pindex - 1);
QuickSort(a, pindex + 1, high);
}
}
int main() {
int n = 7;
int arr[] = {7, 4, 2, 6, 3, 1, 5};
QuickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}실행 결과:
1 2 3 4 5 6 7
퀵 정렬의 시간 복잡도
최선의 경우: O(n log n) — 피벗이 매번 배열을 균등하게 분할할 때
평균의 경우: O(n log n) — 대부분의 실제 데이터에서 기대되는 성능
최악의 경우: O(n²) — 이미 정렬된 배열 등에서 피벗 선택이 불균형할 때
공간 복잡도: O(log n) — 재귀 호출 스택 깊이만큼의 추가 메모리 사용
무작위 피벗 방식을 사용하면 최악의 경우가 발생할 확률을 크게 낮출 수 있어, 실무에서도 널리 활용되는 안정적인 성능을 기대할 수 있습니다.