요약
- Quick Sort는 피벗 선택에 따라 성능이 결정되는 분할 정복 알고리즘
- 피벗이 잘 선택되면 O(N log N), 최악의 피벗 선택이 반복되면 O(N²)
본문
핵심 동작 원리
- 피벗(pivot)을 선택한다
- 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 파티션한다
- 좌/우 부분 배열에 대해 재귀적으로 반복한다
[3, 6, 2, 7, 1] 피벗=3
↓ 파티션
[1, 2] 3 [6, 7]
시간 복잡도 분석
평균 O(N log N): 피벗이 배열을 절반씩 나눌 때
- 재귀 깊이: log N
- 각 단계에서 N번 비교
- N × log N = O(N log N)
최악 O(N²): 피벗이 항상 최솟값/최댓값일 때
[1, 2, 3, 4, 5] 피벗=1
↓
[] 1 [2, 3, 4, 5] 피벗=2
↓
[] 2 [3, 4, 5] ...재귀 깊이 = N
- 이미 정렬된 배열에서 첫 번째/마지막 원소를 피벗으로 선택할 때 발생
- N번 재귀 × N번 비교 = O(N²)
최악을 피하는 방법
- 랜덤 피벗 선택: 무작위로 피벗을 선택하여 특정 입력 패턴에 취약해지는 것을 방지
- Median of Three: 첫 번째, 중간, 마지막 원소 중 중간값을 피벗으로 선택
공간 복잡도
- 평균 O(log N): 재귀 호출 스택의 깊이
- 최악 O(N): 편향된 분할이 반복될 때 스택 깊이가 N까지 증가
in-place 정렬이라 별도 배열이 필요 없지만, 재귀 스택 공간이 필요하다.
Merge Sort와 비교
| Quick Sort | Merge Sort | |
|---|---|---|
| 시간 (평균) | O(N log N) | O(N log N) |
| 시간 (최악) | O(N²) | O(N log N) |
| 공간 | O(log N) | O(N) |
| 안정성 | 불안정 | 안정 |
Merge Sort는 병합 시 임시 배열 O(N)이 필요하지만, Quick Sort는 swap으로 제자리에서 파티션하므로 추가 배열이 불필요하다.