정렬 안내서 · 4/6
정렬 알고리즘은 시간 복잡도만으로 고르지 않습니다. 최선 · 평균 · 최악의 차이, 추가 메모리, 안정성, 입력 패턴에 대한 민감도를 함께 봐야 합니다. 이 장에서는 주요 정렬의 복잡도를 정리하고, 비교 정렬의 하한이 왜 n log n인지, 그리고 계수 · 기수 정렬이 그 하한을 어떻게 피하는지 살펴봅니다.
| 알고리즘 | 최선 | 평균 | 최악 | 추가 메모리 | 안정 | 제자리 |
|---|---|---|---|---|---|---|
| 버블 정렬(조기 종료) | O(n) | O(n²) | O(n²) | O(1) | 예 | 예 |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | O(1) | 아니오 | 예 |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | O(1) | 예 | 예 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | O(n) | 예 | 아니오 |
| 퀵 정렬(무작위 기준값) | O(n log n) | O(n log n) | O(n²) | O(log n) 스택 | 아니오 | 예 |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | O(1) | 아니오 | 예 |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | 예 | 아니오 |
| 인트로소트 | O(n log n) | O(n log n) | O(n log n) | O(log n) | 아니오 | 예 |
| 계수 정렬 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 예 | 아니오 |
| 기수 정렬 | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | 예 | 아니오 |
k는 값의 범위, d는 자릿수, b는 한 자릿수가 가질 수 있는 값의 개수(기수)입니다. 퀵 정렬의 스택 O(log n)은 작은 쪽만 재귀하는 구현에서 성립하며, 단순하게 양쪽을 모두 재귀하면 최악에 O(n)까지 깊어집니다.
병합 정렬의 시간은 점화식 T(n) = 2T(n/2) + O(n)으로 표현됩니다. 크기 n을 반씩 나누면 깊이가 log n이고, 각 깊이에서 합치는 일의 총량이 n이므로 O(n log n)입니다. 입력이 어떻든 똑같이 나누므로 최선과 최악이 같습니다.
퀵 정렬은 기준값이 배열을 얼마나 고르게 나누느냐에 달려 있습니다. 매번 반으로 나누면 병합 정렬과 같은 O(n log n)이고, 매번 한쪽이 비면 n + (n - 1) + ... + 1 = O(n²)입니다. 무작위 기준값을 쓰면 기대 비교 횟수가 약 1.39 n log₂ n으로, 병합 정렬보다 비교는 조금 많지만 제자리에서 연속된 메모리를 훑기 때문에 실제로는 대개 더 빠릅니다. 정렬된 입력에 "첫 원소를 기준값으로" 쓰는 순진한 구현이 얼마나 나빠지는지 직접 세어 볼 수 있습니다.
import random
def quicksort_count(a, choose):
comparisons = 0
stack = [(0, len(a) - 1)]
while stack:
lo, hi = stack.pop()
if lo >= hi:
continue
p = choose(lo, hi)
a[p], a[hi] = a[hi], a[p]
pivot, i = a[hi], lo
for j in range(lo, hi):
comparisons += 1
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
stack += [(lo, i - 1), (i + 1, hi)]
return comparisons
n = 2000
print(quicksort_count(list(range(n)), lambda lo, hi: lo)) # 1999000 = n(n-1)/2
print(quicksort_count(list(range(n)), lambda lo, hi: random.randint(lo, hi))) # 대략 25000 안팎비교 정렬은 "a < b인가?"라는 예/아니오 질문만으로 순서를 알아내야 합니다. 가능한 모든 질문의 흐름을 트리로 그리면(결정 트리), 각 잎은 입력의 한 가지 순열에 대응합니다. 서로 다른 n개의 원소를 늘어놓는 방법은 n!가지이므로 잎이 적어도 n!개 필요하고, 높이가 h인 이진 트리의 잎은 최대 2^h개입니다. 따라서 2^h ≥ n!, 즉 h ≥ log₂(n!)입니다. n!은 적어도 (n/2)^(n/2)이므로 log₂(n!) ≥ (n/2) log₂(n/2)가 되어, 최악의 비교 횟수는 Ω(n log n)입니다.
이 결과는 병합 정렬과 힙 정렬이 점근적으로 최적이라는 뜻입니다. 동시에 "비교만 쓴다"는 전제를 버리면 더 빨라질 수 있다는 뜻이기도 합니다.
import math
for n in [10, 100, 1000]:
lower = math.ceil(math.log2(math.factorial(n)))
print(n, lower, round(n * math.log2(n)))
# 10 22 33
# 100 525 664
# 1000 8530 9966계수 정렬은 값의 범위 k가 n과 비슷하거나 작을 때 O(n + k)에 정렬합니다. 나이, 점수(0~100), 바이트 값처럼 범위가 좁은 정수에 적합하지만, k가 크면 메모리와 시간이 k에 끌려갑니다.
기수 정렬은 w비트 정수를 r비트씩 나누어 d = w / r번 안정적인 계수 정렬을 합니다. 32비트 정수를 8비트씩 나누면 d = 4, b = 256이므로 4(n + 256), 사실상 선형입니다. 문자열도 고정 길이라면 같은 방식으로 정렬할 수 있습니다.
def radix_sort(a, bits=32, r=8):
mask = (1 << r) - 1
for shift in range(0, bits, r):
buckets = [[] for _ in range(1 << r)]
for x in a: # 앞에서부터 넣으므로 안정적
buckets[(x >> shift) & mask].append(x)
a = [x for bucket in buckets for x in bucket]
return a
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]이 구현은 음이 아닌 정수만 다룹니다. 음수는 부호 비트를 뒤집거나 따로 나누어 처리해야 합니다.
O(n log n)이고, 퀵 정렬은 평균이 빠르지만 최악 O(n²)을 기준값 선택으로 막아야 합니다.Ω(n log n)보다 빠를 수 없습니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.