퀵 정렬과 피벗 선택
Lomuto 및 Hoare 분할 방식을 사용해 퀵 정렬을 구현하고, 최악의 경우 O(n²)이 되는 이유와 무작위 피벗 선택으로 이를 완화하는 방법을 알아봅니다.
퀵 정렬과 피벗 선택은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
퀵 정렬: 제자리 분할 정복
퀵 정렬은 실제로 가장 널리 사용되는 정렬 알고리즘입니다. 병합 정렬과 달리 추가 배열을 할당하지 않고 제자리에서 정렬합니다. 핵심 아이디어는 다음과 같습니다. 피벗 원소를 선택하고, 피벗보다 작은 모든 원소가 피벗 앞에 오고 큰 모든 원소가 뒤에 오도록 배열을 분할한 다음, 각 분할을 재귀적으로 정렬합니다. 분할 단계에는 O(n) 시간이 걸리며, 피벗을 잘 선택하면 재귀 깊이는 O(log n)입니다.
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
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
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]룸토 분할 방식
룸토 분할은 마지막 원소를 피벗으로 사용합니다. 느린 포인터 i는 '피벗보다 작은' 영역의 경계를 추적하고, 빠른 포인터 j는 앞으로 이동하며 탐색합니다. arr[j] <= pivot이면 i를 증가시키고 arr[i]와 arr[j]를 교환하여 작은 원소 영역을 확장합니다. 탐색이 끝나면 arr[hi]와 교환하여 피벗을 i+1 위치에 놓습니다. 구현은 간단하지만 호어 방식보다 교환 횟수가 3배 많습니다.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+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]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)호어 분할 방식
호어 분할은 양쪽 끝에서 시작하는 두 포인터를 사용하며, 두 포인터가 교차할 때까지 안쪽으로 이동합니다. 피벗(일반적으로 첫 번째 원소)을 선택하고, 피벗보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 이동합니다. 호어 방식은 룸토 방식보다 교환 횟수가 3배 적고 동일한 원소가 있을 때 더 잘 작동하지만, 분할이 끝난 뒤에도 피벗이 최종 위치에 놓이지 않습니다. 따라서 재귀 호출이 약간 달라집니다.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]최악의 경우 O(n²): 이미 정렬된 입력
퀵 정렬의 최악의 경우는 피벗이 분할에서 계속해서 가장 작거나 가장 큰 원소로 선택될 때 발생합니다. 이미 정렬된 배열에서 룸토의 마지막 원소 피벗을 사용하면 분할 결과는 항상 왼쪽에 원소 0개, 오른쪽에 n-1개가 놓입니다. 재귀 트리는 깊이 n인 사슬로 퇴화하고 비교 횟수는 O(n²)이 됩니다. 이것이 피벗 선택이 중요한 이유이며, 실제 구현에서 피벗을 무작위화하는 이유입니다.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2무작위 피벗: 기대 시간 O(n log n)
피벗을 균등하게 무작위로 선택하면(분할하기 전에 무작위 원소를 arr[hi]와 교환), 좋지 않은 피벗을 계속 선택할 확률이 지수적으로 낮아집니다. 비교 횟수의 기댓값은 2n ln(n) ≈ 1.39 n log₂(n)이므로, 기대 시간은 O(n log n)이며 압도적으로 높은 확률로 이 시간 복잡도를 얻습니다. 이것이 무작위 퀵 정렬이 실제로 사용되는 이유입니다. 고정 피벗 전략에 대해 공격자가 만들어 낼 수 있는 병적인 최악의 경우를 피할 수 있습니다.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
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]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]세 원소의 중앙값 피벗
또 다른 피벗 전략은 첫 번째, 중간, 마지막 원소의 중앙값을 선택하는 것입니다. 이렇게 하면 가장 흔한 공격적 입력인 정렬된 입력이나 역순으로 정렬된 입력에서 최악의 동작을 피하면서도 난수 생성 오버헤드를 피할 수 있습니다. 많은 실제 구현에서는 큰 배열에 세 원소의 중앙값 또는 나인더(세 중앙값의 중앙값)를 사용하고, 약 10개 원소라는 임계값보다 작은 부분 배열에는 삽입 정렬로 전환합니다.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
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]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)네덜란드 국기: 세 방향 분할
표준 분할은 피벗보다 작은 원소를 왼쪽에, 큰 원소를 오른쪽에 배치하지만 피벗과 같은 원소는 흩어집니다. 세 방향 분할(네덜란드 국기)은 세 영역을 만듭니다. <pivot, ==pivot, >pivot. 중복 원소가 많은 배열에서는 이것이 매우 중요합니다. 표준 퀵 정렬은 O(n²)로 느려질 수 있지만 세 방향 퀵 정렬은 모든 원소가 같은 값인 입력에서 O(n)을 얻습니다.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)퀵셀렉트: O(n)에 k번째 최솟값 찾기
퀵셀렉트는 퀵 정렬의 분할 단계를 사용하여 전체를 정렬하지 않고 평균 O(n) 시간에 k번째 최솟값을 찾습니다. 분할이 끝나면 피벗은 최종 위치 p에 있습니다. p == k이면 arr[p]를 반환합니다. k < p이면 왼쪽 분할에서 재귀를 수행하고, k > p이면 오른쪽 분할에서 재귀를 수행합니다. 평균적으로 각 재귀 단계에서 문제의 크기가 절반으로 줄어듭니다. O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n)입니다.
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)퀵 정렬의 공간 복잡도
퀵 정렬은 '제자리' 알고리즘이라고 하지만 재귀를 위해 평균 O(log n)의 스택 공간을 사용합니다(재귀 트리의 수준마다 프레임 하나). 최악의 경우 스택 깊이는 O(n)이 됩니다. 최악의 경우에도 O(log n) 스택 공간을 보장하려면 항상 더 작은 분할에 먼저 재귀를 적용하고 더 큰 분할에는 꼬리 호출 최적화를 사용해야 합니다. 파이썬의 재귀 제한 때문에 매우 깊은 퀵 정렬 재귀는 위험할 수 있으므로, 면접에서 언급할 만한 내용입니다.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(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정렬 알고리즘 비교
지식을 종합해 보십시오.
- 퀵 정렬: 기대 시간 O(n log n), 최악의 경우 O(n²), 공간 O(log n), 불안정, 무작위 데이터에서 실제로 가장 빠름
- 병합 정렬: O(n log n) 보장, 공간 O(n), 안정적, 연결 리스트와 외부 정렬에 적합
- 힙 정렬: O(n log n) 보장, 공간 O(1), 불안정, 캐시 누락 때문에 실제로는 더 느림
- 삽입 정렬: 최선의 경우 O(n), 작은 n 또는 거의 정렬된 데이터에 적합
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elements인트로소트: 세 알고리즘의 결합
인트로소트(C++ STL에서 std::sort에 사용됨)는 퀵 정렬, 힙 정렬, 삽입 정렬을 결합합니다. 무작위 퀵 정렬로 시작하고, 재귀 깊이가 2 log n을 초과하면(좋지 않은 피벗 선택이 이어지고 있음을 나타냄) 힙 정렬로 전환하여 O(n log n)을 보장합니다. 원소 16개보다 작은 부분 배열에는 삽입 정렬을 사용합니다. 이렇게 하면 최악의 경우 O(n log n)을 보장하면서 퀵 정렬의 평균적인 속도와 작은 부분 배열에서 삽입 정렬의 효율성을 얻을 수 있습니다.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))빠른 확인
이 학습에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
학습 내용 정리
이 학습에서는 퀵 정렬이 피벗을 기준으로 제자리 분할을 수행하고 양쪽에 재귀를 적용하여 O(n log n)의 기대 시간과 O(log n)의 스택 공간을 달성하며, 무작위 데이터에서는 실제로 병합 정렬보다 빠르다는 것, 고정 피벗을 사용하는 정렬된 입력에서 최악의 경우 O(n²)이 발생하고 무작위 피벗 선택이나 세 원소의 중앙값으로 이를 피할 수 있다는 것, 그리고 세 방향 분할은 중복 원소를 효율적으로 처리하며, 퀵셀렉트는 분할 개념을 확장하여 전체를 정렬하지 않고 평균 O(n) 시간에 k번째 최솟값을 찾는다는 것을 배웠습니다. 다음에는 비비교 정렬과 파이썬의 내장 정렬을 살펴봅니다.
자주 묻는 질문
“퀵 정렬과 피벗 선택” 강의는 무료인가요?
네 — “퀵 정렬과 피벗 선택” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“퀵 정렬과 피벗 선택”에서 뭘 배우나요?
Lomuto 및 Hoare 분할 방식을 사용해 퀵 정렬을 구현하고, 최악의 경우 O(n²)이 되는 이유와 무작위 피벗 선택으로 이를 완화하는 방법을 알아봅니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“퀵 정렬과 피벗 선택” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.