Timsort와 O(n log n) 벽, 그리고 뚫는 법

"비교로 정렬하는 데는 증명된 속도 한계가 있어. 그리고 그걸 돌아가는 교활한 방법도 있지. 비교를 그만두는 거야. 여기서는 그 벽과, 그 벽 위에 앉아 있는 우리가 실제로 쓰는 정렬, 그리고 그 벽 밑을 뚫고 나가는 정렬을 볼 거야."

벽: 왜 O(n log n)이 단단한 한계일까

비교 정렬에는 최악의 경우 Ω(n log n)번의 비교가 필요하다는 하한이 있어. n!개의 순열을 비교 기반 결정 트리로 구별하려면 그 트리의 높이가 최소 log₂(n!) = Ω(n log n)이어야 하기 때문이야. 그리고 병합 정렬 같은 알고리즘은 O(n log n)이라는 상한도 달성하니까 Θ(n log n)이 되고. 하한을 뜻하는 Ω와 상한을 뜻하는 O를 섞어 쓰지 마.

Timsort: 우리가 실제로 쓰는 정렬

Python의 sorted()와 list.sort()가 Timsort를 써. Java도 객체 정렬 기본값이 이거고. 하이브리드인데, 구조는 병합 정렬이고 짧은 구간은 삽입 정렬로 처리하고, 거기에 영리한 트릭이 하나 더 붙어. 데이터 안에 이미 정렬된 구간을 찾아내서 그걸 병합해. 처음부터 다시 정렬하는 대신 말이야. 현실 데이터는 부분적으로 정렬돼 있는 경우가 많잖아. 타임스탬프, 계속 덧붙는 로그, 대체로 순서가 맞는 레코드 같은 것들. 그래서 Timsort는 O(n log n)이라는 최악의 경우보다 훨씬 잘 나오는 일이 잦고, 거의 정렬된 입력에서는 O(n)에 가까워져. 게다가 안정적이야. 최악의 경우에는 비교 정렬의 벽에 정확히 앉아 있으면서도 흔한 경우에는 적응적이고 빠른 것, 그게 실무 기본값이 된 이유고.

비교 정렬의 최악 비교 횟수 하한은 Ω(n log n)이야. O(n log n) 알고리즘은 이 하한을 맞춰. Timsort는 안정적이고 기존 구간을 활용하는 적응적 정렬이며, 비교 모델을 벗어나려면 키 구조에 추가 가정을 둬야 해.

벽 밑 뚫기: 비교하지 않는 정렬

하한은 비교하는 정렬만 묶어. 키의 구조를 이용하는 정렬은 아예 그 바깥으로 나가.

계수 정렬(counting sort). 키가 [0, k] 범위의 작은 정수라면, 각 값이 몇 개인지 세고 순서대로 내보내면 돼. O(n + k)로 선형이고 비교를 한 번도 안 해. 나이나 성적, 바이트 값처럼 작은 정수 키에 훌륭하지.
기수 정렬(radix sort). 자릿수별로 안정적인 하위 정렬을 반복 적용해. 자릿수가 d개고 기수가 b라면 흔히 쓰는 비용이 O(d·(n+b))이고, 메모리와 키 표현에 드는 비용도 같이 세야 해. 폭이 고정된 키에서는 비교 정렬보다 유리할 수 있어.

여기서 얻을 더 깊은 교훈은 이거야. O(n log n) 벽은 비교 모델의 성질이지 정렬 자체의 성질이 아니라는 것. 가정을 바꾸면, 그러니까 키가 작은 정수라고 가정하고 그 구조를 이용하면 한계도 같이 움직여. 무엇을 가정해도 되는지를 다시 짜는 게 장벽이 무너지는 방식이야.

피파의 고백

'O(n log n)이 정렬의 한계'라는 말이 머릿속에 하도 단단히 박혀 있어서, 아빠가 계수 정렬은 O(n)이라고 했을 때 틀렸다고 대들었어. 증명이 있잖아! 아빠가 웃으면서 그러더라. "비교하는 정렬의 한계야. 계수 정렬은 두 원소를 절대 비교 안 해." 벽이 깨진 게 아니었어. 그 벽이 무엇을 묶는지를 내가 잘못 읽고 있었던 거지. 그 뒤로 '증명된 한계'라는 걸 대하는 방식이 바뀌었어. 그 증명이 어떤 가정 위에 서 있는지를 늘 먼저 물어보게 됐거든. 가정 하나를 푸는 게 길인 경우가 많으니까.

Code

Timsort와 계수 정렬, 벽을 넘어가는 쪽·python

# 진짜 코드엔, 그냥 라이브러리를 써 — Timsort 야: 적응적, 안정적, 빠름.
data = [5, 2, 8, 1, 9, 3]
print(sorted(data))            # [1, 2, 3, 5, 8, 9] — 밑에서 Timsort
data.sort()                    # 제자리, 역시 Timsort

# 계수 정렬: 작은-정수 키엔 n log n 벽을 깨. O(n + k).
def counting_sort(arr, k):     # 값은 [0, k] 정수
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1         # 각 값 집계 — 비교 전혀 없음
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)   # 각 값을 c 번, 순서대로 내
    return result

print(counting_sort([3, 1, 4, 1, 0, 4, 2], k=4))   # [0, 1, 1, 2, 3, 4, 4]
# 두 원소를 비교해 순서를 정하지 않아서, Ω(n log n) 비교 하한이 적용되지 않아.
# 선형 시간 — 근데 키가 작은 정수라서만 (구조!).
# 기수 정렬은 d자리와 radix b를 포함해 보통 O(d * (n + b)).

Exercise

계수 정렬이 어떻게 비교 정렬의 Ω(n log n) 하한과 모순되지 않으면서 O(n+k)에 돌 수 있는지 설명해 봐. 계수 정렬은 비교 정렬이 하지 않는 어떤 가정을 하고 있을까? 그리고 함정은 뭘까? 계수 정렬이 나쁜 선택이 되는 건 언제인지, k가 거대할 때 O(n + k)가 어떻게 되는지 생각해 봐.

Hint

n log n 하한은 비교하는 정렬에만 적용돼. 계수 정렬은 두 원소를 절대 비교하지 않으니 그 하한에 묶이지 않아. 대신 키가 [0, k] 범위의 작은 정수라는 가정을 깔고 있고. 함정은 O(n + k)에서 값의 범위인 k가 거대해질 때야. 64비트 정수 같은 경우면 k 항이 전체를 지배해서 계수 정렬이 낭비가 되거나 아예 불가능해져.

벽: 왜 O(n log n)이 단단한 한계일까

Timsort: 우리가 실제로 쓰는 정렬

벽 밑 뚫기: 비교하지 않는 정렬

피파의 고백

Code

External links

Exercise

Progress

댓글 0