Quick Flow
| 항목 | 특징 |
|---|---|
| 평균 시간 | O(n log n) |
| 최악 시간 | O(n²) |
| 추가 공간 | 재귀 스택, 평균 O(log n) |
| 핵심 위험 | 나쁜 피벗 선택 |
pivot을 고른다
pivot보다 작은 값과 큰 값을 나눈다
왼쪽과 오른쪽을 다시 정렬한다평균 성능과 제자리 분할이 필요할 때 선택하지만, 피벗이 계속 치우치면 O(n²)입니다. 최악 시간 보장이나 안정성이 필요하면 다른 정렬을 고릅니다.
구조
퀵 정렬은 피벗을 하나 고르고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 보내는 정렬입니다. 분할이 균형 잡히면 깊이가 log n에 가까워지고, 각 깊이에서 전체를 훑으므로 평균 O(n log n)이 됩니다.
[5, 1, 4, 2, 3], pivot = 3
-> [1, 2] 3 [5, 4]
-> 왼쪽 정렬 + 오른쪽 정렬피벗 선택
피벗이 매번 최솟값이나 최댓값이 되면 한쪽 구간만 줄어듭니다. 이 경우 재귀 깊이가 n이 되고 전체 시간이 O(n²)이 됩니다.
좋은 분할: n/2 + n/2
나쁜 분할: 0 + n-1그래서 실제 구현에서는 가운데 값, 랜덤 피벗, median-of-three 같은 방법으로 치우침을 줄입니다.
3-way partition
중복 값이 많을 때는 pivot보다 작은 구간, 같은 구간, 큰 구간을 한 번에 나눕니다. 같은 값 구간을 다시 재귀하지 않아 all-equal 입력에서도 한쪽으로 깊어지는 문제를 줄입니다.
static void QuickSort(int[] values)
{
var random = Random.Shared;
void Sort(int left, int right)
{
if (left >= right) return;
int pivot = values[random.Next(left, right + 1)];
int less = left;
int current = left;
int greater = right;
while (current <= greater)
{
if (values[current] < pivot)
{
(values[less], values[current]) = (values[current], values[less]);
less++;
current++;
}
else if (values[current] > pivot)
{
(values[current], values[greater]) = (values[greater], values[current]);
greater--;
}
else
{
current++;
}
}
Sort(left, less - 1);
Sort(greater + 1, right);
}
Sort(0, values.Length - 1);
}랜덤 피벗은 평균적인 치우침을 줄일 뿐 최악 시간을 없애지는 않습니다. 재귀 깊이가 제한되는 환경에서는 작은 구간을 먼저 재귀하고 큰 구간은 반복으로 처리하거나 표준 정렬 API를 사용합니다.
선택 기준
| 상황 | 판단 |
|---|---|
| 평균 성능과 in-place가 중요 | 퀵 정렬 적합 |
| 최악 시간 보장이 중요 | 병합 정렬, 힙 정렬 검토 |
| 중복 값이 많음 | 3-way partition 검토 |
| stable 정렬 필요 | 일반 퀵 정렬은 부적합 |
| 표준 정렬 API 가능 | 직접 구현보다 API 우선 |
퀵 정렬은 개념상 강력하지만, 코딩 테스트에서 직접 구현할 때는 피벗과 중복 처리 때문에 실수가 많습니다. 정렬 자체가 목적이면 표준 API를 쓰고, 문제에서 분할 아이디어를 요구할 때만 직접 구현을 고려하는 편이 안전합니다.
주의할 점
이미 정렬된 배열에 첫 원소를 피벗으로 쓰는 퀵 정렬은 최악 O(n²)이 되기 쉽습니다. 입력이 적대적으로 들어올 수 있는 코테에서는 피벗 선택을 방어적으로 해야 합니다.
또 분할 과정에서 같은 값 처리 기준이 불명확하면 무한 루프가 생기거나 한쪽으로 값이 몰릴 수 있습니다.
참고 링크
1 sources