~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
"병합 정렬은 가운데를 눈 감고 자르지. 퀵소트는 피벗을 중심으로 영리하게 나눠. 그 영리함이 대개 더 빠르게 만들고 가끔은 재앙으로 만들어. 승부는 전부 피벗을 어떻게 고르느냐에 달렸어."
알고리즘
퀵소트도 훌륭한 분할 정복 정렬인데, 재귀한 뒤가 아니라 재귀하기 전에 일을 해. 먼저 피벗이 될 원소를 하나 골라. 그다음 피벗보다 작은 건 전부 왼쪽으로, 큰 건 전부 오른쪽으로 가도록 배열을 분할해. 이 시점에 피벗은 이미 최종 정렬 위치에 있어. 그러고 나서 왼쪽 부분과 오른쪽 부분을 각각 재귀로 퀵소트하면 돼. 병합 단계는 없어. 양쪽이 정렬되는 순간 전체가 이미 정렬돼 있으니까. 영리한 일은 분할이 다 하고 합치기는 공짜야.
왜 보통 가장 빠를까
전통적인 배열 퀵소트의 강점은 제자리 분할과 좋은 캐시 지역성이야. 다만 아래에 있는 교육용 Python 코드는 리스트 컴프리헨션으로 less, equal, greater를 새로 만들기 때문에 제자리 구현이 아니야. 알고리즘 설명과 예제 코드의 메모리 모델을 섞지 마. 실제 성능도 구현과 입력 분포에 달려 있고.
함정: 나쁜 피벗이 O(n²)를 부른다
피벗이 계속 한쪽으로 치우쳐 떨어지면 퀵소트는 O(n²)이 돼. 무작위 피벗을 쓰면 특정 입력이 매번 나쁜 피벗을 강제하지 못하게 막아 줘서 기대값이 O(n log n)이 되지만, 최악의 O(n²) 자체를 없애는 건 아니야. 최악 시간에 대한 보장이 필요하다면 introsort처럼 깊이 제한을 넘으면 다른 정렬로 갈아타는 방식을 써. 그리고 전통적인 퀵소트는 안정 정렬도 아니야.
퀵소트는 피벗을 고르고, 피벗보다 작은 쪽과 큰 쪽으로 분할하고(이때 피벗은 제자리에 안착), 양쪽을 재귀해. 제자리에서 돌고 캐시에 유리해서 실전에서 대개 가장 빠르고 평균이 O(n log n)이야. 다만 피벗이 나쁘면 O(n²)이 되니 피벗을 무작위로 골라 막아야 해. 안정 정렬은 아니고.
보너스: 퀵셀렉트
분할이라는 아이디어에서 멋진 파생이 하나 나와. 완전히 정렬하지 않고 k번째로 작은 원소만 찾고 싶다면, 한 번만 분할해 봐. 피벗이 어떤 위치 p에 안착하겠지. p가 k와 같으면 끝이야. k가 p보다 작으면 왼쪽 부분만 재귀하고, 아니면 오른쪽만 재귀해. 한쪽만 재귀하니까 이 퀵셀렉트가 평균 O(n)에 돌아가. 완전한 O(n log n) 정렬을 치르지 않고도 중앙값이나 '순위 기준 상위 k'를 찾을 수 있는 거지. 전부 정렬해야 한다는 의무에서 풀려난 분할 단계인 셈이야.
피파의 고백
내 퀵소트가 테스트에서는 아름답게 돌다가 실서비스 데이터셋에서 얼어붙었어. 데이터가 이미 정렬돼 있었고 나는 매번 첫 원소를 피벗으로 고르고 있었거든. 교과서에 나오는 O(n²) 그대로였지. 아빠의 한 줄짜리 수정은 피벗을 무작위로 고르는 거였고, 그러자 멈춤 현상이 사라졌어. 그때 교훈이 깊이 박혔어. 퀵소트의 평균적인 명석함이 진짜로 정렬된 데이터가 대놓고 불러내는 최악의 경우를 가리고 있다는 것. 피벗 무작위화는 있으면 좋은 마감이 아니라 퀵소트를 내보내도 되게 만드는 조건이야.
Code
퀵소트와 퀵셀렉트 (한쪽만 재귀)·python
import random
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # 기대 O(n log n), 최악 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.