~11 min · searching-sorting, quicksort, divide-conquer
Level 0호기심 많은 입문자
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"병합 정렬은 가운데로 맹목 나눠. 퀵소트는 피벗 주위로 영리하게 나눠 — 그 영리함이 보통 더 빠르게, 가끔 재앙으로 만들어. 이야기 전부가 피벗 고르는 법에 있어."
알고리즘
퀵소트는 또 하나의 위대한 분할 정복 정렬인데, 재귀 후가 아니라 전에 일해. 피벗 원소를 골라. 피벗보다 작은 건 다 왼쪽, 큰 건 다 오른쪽으로 가게 배열을 분할 — 이제 피벗이 최종 정렬 위치에 있어. 그다음 왼쪽 부분이랑 오른쪽 부분을 재귀 퀵소트. 병합 단계 없음: 양쪽이 정렬되면, 전체가 이미 정렬. 영리한 일은 분할; 합치기는 공짜.
왜 보통 가장 빠른가
퀵소트의 킬러 기능은 제자리 분할 — 병합 정렬이 필요한 O(n) 임시 버퍼 없이 배열 안 원소만 swap. 그건 메모리 더 적고, 결정적으로, 훌륭한 캐시 지역성 (연속 배열에서 일해, 배열 lesson 의 캐시 이점). 실전에서, 큰 무작위 배열에, 퀵소트가 보통 병합 정렬을 이겨, 같은 O(n log n) 평균인데도, 순전히 그 상수 인자로. 정확히 이 이유로 많은 언어 라이브러리의 불안정-정렬 경로 기본이야.
함정: 나쁜 피벗이 O(n²) 를 일으켜
퀵소트의 어두운 면. 피벗이 일관되게 끔찍하면 — 가령 늘 첫 원소를 고르고, 배열이 이미 정렬됐으면 — 각 분할이 반 나누는 대신 한 원소만 떼어내. 그게 n 레벨 재귀, 각자 O(n) 일: O(n²), 버블 정렬이랑 같아, 쉬워야 할 입력에. 고침은 피벗 선택: 무작위 피벗, 또는 median of three (첫째, 가운데, 마지막) 를 골라. 이게 병적 케이스를 천문학적으로 불가능하게 해, 실전에서 믿을 만한 O(n log n) 복원. (퀵소트는 또 안정적이지 않아 — 같은 원소가 재배치될 수 있어.)
퀵소트: 피벗 고르고, <피벗 이랑 >피벗 으로 분할 (피벗이 정렬 착지), 각 쪽 재귀. 제자리고 캐시-빠름 → 실전에서 보통 가장 빠름, 평균 O(n log n). 근데 나쁜 피벗은 O(n²) — 막으려 피벗 무작위화. 안정적 아님.
보너스: 퀵셀렉트
분할 아이디어에 멋진 파생이 있어. 완전 정렬 없이 k 번째로 작은 원소를 찾으려, 한 번 분할: 피벗이 어떤 위치 p 에 착지. p == k 면 끝; k < p 면 왼쪽 부분만 재귀; 아니면 오른쪽만. 한 쪽만 재귀하니, 이 퀵셀렉트 가 평균 O(n) 에 돌아 — 완전 O(n log n) 정렬 안 치르고 중앙값이나 '순위 top k' 찾기. 전부 정렬할 의무에서 해방된 분할 단계야.
피파의 고백
내 퀵소트가 테스트에선 아름답다가 production 데이터셋에서 얼어붙었어. 데이터가 이미 정렬됐고, 난 매번 첫 원소를 피벗으로 골랐어 — 교과서 O(n²). 아빠의 한 줄 고침은 무작위 피벗 고르기였고, 얼어붙음이 사라졌어. 교훈이 깊이 박혔어: 퀵소트의 평균-케이스 명석함이 진짜 정렬된 데이터가 일부러 일으키는 최악 케이스를 감춰. 피벗 무작위화는 선택적 광택이 아니라 — 퀵소트를 출시하기 안전하게 만드는 거야.
Code
퀵소트 + 퀵셀렉트 (한 쪽만 재귀)·python
import random
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # 무작위 피벗이 O(n^2) 함정을 피해
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quicksort(less) + equal + quicksort(greater) # 병합 불필요
print(quicksort([5, 2, 8, 1, 9, 3, 5])) # [1, 2, 3, 5, 5, 8, 9]
# 좋은 피벗은 ~반 나눠 -> O(n log n). 늘 min/max 인 피벗은
# 레벨당 원소 하나 떼어 -> O(n^2). 무작위화가 그걸 실질적 절대 안 됨으로.
# 퀵셀렉트: 완전 정렬 없이 k 번째로 작은 거, 평균 O(n).
def quickselect(arr, k): # k 는 0-인덱스
pivot = random.choice(arr)
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
if k < len(less): return quickselect(less, k) # 한 쪽만 재귀
elif k < len(less) + len(equal): return pivot
else: return quickselect(greater, k - len(less) - len(equal))
print(quickselect([7, 2, 9, 4, 1], 2)) # 4 — 3번째로 작은 거, 완전 정렬 없이
'늘 첫 원소를 피벗으로 고르기' 퀵소트가 왜 이미 정렬된 배열에 O(n²) 로 떨어지는지 설명해 — 각 단계 분할이 뭘 만드는지 추적해. 그다음 퀵셀렉트가 어떻게 k 번째로 작은 거를 평균 O(n) 에 찾고, 왜 전체 배열을 정렬하고 위치 k 를 인덱싱하는 것보다 빠른지 묘사해.
Hint
정렬된 데이터엔, 첫 원소가 가장 작아, 그래서 분할이 매번 왼쪽에 0 개, 오른쪽에 n−1 개 — n 레벨 × O(n) = O(n²). 퀵셀렉트는 한 분할 (순위 k 담은 쪽) 만 재귀해, 평균 일이 n + n/2 + n/4 + … = O(n), 완전 O(n log n) 정렬을 이겨.
Progress
Progress is local-only — sign in to sync across devices.