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