Ch.8 정렬과 탐색
Quick Sort — 피벗과 파티셔닝
기준을 하나 잡고, 작은 건 왼쪽, 큰 건 오른쪽
100명의 학생을 키 순서로 세울 때, 한 명을 기준(피벗)으로 세우고 작은 사람은 왼쪽, 큰 사람은 오른쪽으로 보냅니다.
피벗을 잘못 고르면 한쪽에 몰리는데, 어떻게 빠를 수 있을까?
좋은 피벗을 고르면 매번 절반으로 나뉘어 O(n log n) — 이것이 Quick Sort의 핵심입니다.
핵심 개념
피벗(Pivot)
배열을 둘로 나누는 기준 원소
파티셔닝
피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치하는 과정
핵심 내용
Quick Sort의 핵심은 파티셔닝 한 단계입니다
[5, 3, 8, 1, 7, 2, 6, 4] — 피벗 = 4 1. 4보다 작은 것: [3, 1, 2] 2. 피벗: [4] 3. 4보다 큰 것: [5, 8, 7, 6] → [3, 1, 2] + [4] + [5, 8, 7, 6] → 각 부분에 재귀 적용
간결한 Python 구현과 In-place 구현을 비교합니다
# 간결한 버전 (추가 공간 사용)
def quick_sort_simple(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x <= pivot]
right = [x for x in arr[:-1] if x > pivot]
return quick_sort_simple(left) + [pivot] + quick_sort_simple(right)# In-place 버전 (면접용)
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi] # 마지막 원소를 피벗
i = lo - 1 # 작은 값의 경계
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1면접에서는 in-place partition을 직접 구현할 수 있어야 합니다
partition([5,3,8,1,4], 0, 4)를 한 줄씩 추적합니다
피벗 4가 정확히 제자리에! 왼쪽은 모두 작고, 오른쪽은 모두 큽니다
Quick Sort의 성능은 피벗 선택에 달려 있습니다
좋은 피벗 — 매번 절반으로 나눔 → 깊이 log n × 각 층 n = O(n log n) 나쁜 피벗 — 이미 정렬된 배열에서 마지막 원소 선택 → 한쪽에 n-1개 몰림 = O(n²)
# 최악 방지: 랜덤 피벗
import random
def partition_random(arr, lo, hi):
rand_idx = random.randint(lo, hi)
arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
return partition(arr, lo, hi)
# 또는 median-of-three
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
return mid면접 답변: "Quick Sort 최악은 O(n²)이지만, 랜덤 피벗으로 확률적으로 O(n log n)을 보장합니다"
두 O(n log n) 정렬의 차이를 비교합니다
| 항목 | Merge Sort | Quick Sort | |------|-----------|------------| | 최악 | O(n log n) | O(n²) | | 공간 | O(n) | O(log n) | | 안정 | ✅ | ❌ | | 캐시 | 나쁨 (비연속) | 좋음 (연속) | | 실전 | Linked List | Array |
배열 정렬은 Quick Sort (캐시 친화), Linked List 정렬은 Merge Sort가 표준 답안입니다
Quick Sort의 최악 시간 복잡도가 O(n²)이 되는 경우는?
Quick Sort는 안정 정렬이다
파티셔닝 마스터!
핵심 용어
피벗 선택
기준 원소를 하나 고른다
파티셔닝
피벗 기준 좌/우로 분리
재귀
좌/우 각각에 같은 작업 반복
정리 노트
Quick Sort — 피벗과 파티셔닝
핵심 개념
- 파티셔닝
- 피벗 기준 좌/우 분리 → 재귀
- 평균
- O(n log n), 최악 O(n²)
- 공간
- O(log n) — in-place + 재귀 스택
면접 포인트
- 최악 방지
- 랜덤 피벗 또는 median-of-three
- vs Merge
- Array→Quick Sort, LinkedList→Merge Sort
면접에서 Quick Sort를 설명할 때 반드시 '최악 O(n²) 방지법'을 언급하세요!
시각 자료
핵심 정리
- 1Quick Sort = 피벗 선택 + 파티셔닝 + 재귀
- 2평균 O(n log n), 최악 O(n²) — 랜덤 피벗으로 방지
- 3Array 정렬의 실전 표준 (캐시 친화적)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작