④
정답 · 평균 O(n²) 아닌 것
퀵 정렬 (Quick Sort)
| ① | 선택 정렬 — 단순 3개 중 하나, O(n²) |
| ② | 삽입 정렬 — 단순 3개 중 하나, O(n²) |
| ③ | 버블 정렬 — 단순 3개 중 하나, O(n²) |
| ④ ✅ | 퀵 정렬 — 분할정복, 평균 O(n log n). 정답. |
합격 공식 + 함정
단순 3(선삽버)=O(n²), 고급 3(퀵·병합·힙)=O(n log n). 단 퀵의 최악은 O(n²) — '퀵은 항상 O(n log n)'은 함정.