빠른 정렬 · 복잡도 노트
출처: 빠른 정렬 · 알고리즘
알고리즘 아이디어
알고리즘- 피벗 선택 -> 분할 -> 양쪽을 재귀 처리
- 제자리 정렬이지만 안정 정렬은 아니다
복잡도 표
알고리즘| 경우 | 시간 | 공간 |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
점화식
알고리즘- T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n)
면접 카드
알고리즘- Q: 무작위 피벗을 쓰는 이유는? 답: 정렬된 입력이나 악의적 입력에서 Θ(n²)을 피하기 위해.



