토픽 9 / 82

퀵 정렬 (Quick Sort)

피벗을 선택하여 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한 후 재귀적으로 정렬하는 분할 정복 기반 알고리즘

목적: 평균 빠른 정렬, 제자리 정렬, 실용적 성능

특징: 분할 정복, 불안정 정렬, 제자리, 피벗 선택 중요

동작: ① 피벗 선택 → ② 분할(피벗 기준 좌우 배치) → ③ 좌우 재귀 정렬

피벗 선택: 첫 요소(간단/최악), 랜덤(평균 좋음), 중간값(3개 중앙값, Median-of-Three)

분할(Partition): 투 포인터, 피벗보다 작은 값 왼쪽, 큰 값 오른쪽, O(n)

시간 복잡도: 최선·평균 O(n log n), 최악 O(n²) - 이미 정렬됨+첫 피벗

공간 복잡도: O(log n) - 재귀 스택, 제자리

최적화: Median-of-Three 피벗, 작은 서브배열은 삽입 정렬, 3-way 분할(중복 많을 때)

장점: 평균 빠름(O(n log n)), 제자리, 캐시 효율, 실용적

단점: 최악 O(n²), 불안정, 피벗 선택 중요, 재귀 깊이

적용사례: 범용 정렬, C qsort(), 대규모 데이터, Intro Sort(퀵+힙+삽입)

비교: 퀵(평균빠름/제자리/최악O(n²)) vs 병합(안정/O(n)공간/보장) vs 힙(보장/느림)

연관: 분할 정복, 병합 정렬, 피벗, Intro Sort