동작 원리: 단계별 추적

이 장에서는 작은 입력으로 네 가지 알고리즘을 손으로 따라가 봅니다. 병합 정렬, 병합하면서 역순 쌍 세기, 빠른 거듭제곱, 퀵셀렉트입니다. 추적을 한 번 직접 해 보면 다음 장의 코드가 훨씬 쉽게 읽힙니다.

여덟 개 수의 병합 정렬

[5, 2, 4, 7, 1, 3, 2, 6]을 예로 듭니다. 조각마다 원소가 하나 남을 때까지 절반으로 자른 뒤, 아래 단계부터 차례로 병합합니다.

단계마다 모든 원소를 한 번씩 다루고 단계 수는 log2 8 = 3입니다. 여기서 O(n log n)이 나옵니다. 병합은 정렬된 두 목록의 맨 앞 원소를 비교해 작은 쪽을 꺼내는 일을 되풀이합니다.

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:    # <= 를 쓰면 같은 값의 순서가 유지된다(안정 정렬)
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

print(merge([2, 4, 5, 7], [1, 2, 3, 6]))  # [1, 2, 2, 3, 4, 5, 6, 7]

병합하면서 역순 쌍 세기

역순 쌍(inversion)은 i < j이면서 a[i] > a[j]인 위치 쌍입니다. 모든 쌍을 확인하면 O(n^2)이 듭니다. 분할 정복에서는 역순 쌍을 세 종류로 나눕니다. 두 원소가 모두 왼쪽 절반에 있는 쌍, 모두 오른쪽 절반에 있는 쌍, 양쪽에 하나씩 있는 쌍(경계를 넘는 쌍)입니다. 앞의 두 종류는 재귀 호출이 세고, 경계를 넘는 쌍은 병합하면서 거의 공짜로 셉니다. right[j]가 left[i]보다 먼저 꺼내지면 그 값은 left[i]와 그 뒤에 남은 왼쪽 원소 모두보다 작으므로 len(left) - i개의 역순 쌍을 만듭니다.

위 추적의 마지막 병합, [2, 4, 5, 7]과 [1, 2, 3, 6]을 따라가 봅니다.

마지막 병합에서 11이 더해집니다. 아래 단계에서는 [5]와 [2]의 병합에서 1, [2, 5]와 [4, 7]에서 1(4가 5보다 작음), [1, 3]과 [2, 6]에서 1(2가 3보다 작음)이 더해지므로 이 배열의 역순 쌍은 모두 14개입니다. 값이 같을 때(2 <= 2) 왼쪽을 먼저 꺼내므로 같은 값은 역순 쌍으로 세지 않습니다.

빠른 거듭제곱

e가 크면 b를 e - 1번 곱하는 방법은 쓸 수 없습니다. 대신 지수를 절반으로 줄입니다. e가 짝수면 b^e = (b^(e/2))^2, 홀수면 b^e = (b^((e-1)/2))^2 * b입니다. 호출마다 e가 절반이 되므로 곱셈은 많아야 약 2 log2 e번입니다.

3^13을 추적해 봅니다(13은 이진수로 1101).

def power(b, e):
    if e == 0:
        return 1
    half = power(b, e // 2)
    return half * half * b if e % 2 else half * half

print(power(3, 13))  # 1594323

곱셈 열두 번이 호출 다섯 번으로 줄었습니다. e = 10^18이라면 10^18단계 대신 약 60번의 호출로 끝납니다.

퀵셀렉트

퀵셀렉트는 전체를 정렬하지 않고 k번째(0부터)로 작은 원소를 찾습니다. 퀵 정렬처럼 피벗을 기준으로 분할한 뒤, 위치 k가 들어 있는 쪽에서만 계속합니다.

마지막 원소를 피벗으로 쓰는 경우를 a = [7, 2, 9, 4, 1, 8, 3], k = 3으로 추적합니다.

첫 단계 이후로는 분할할 때마다 원소가 하나씩만 줄어듭니다. 피벗을 잘못 고르면 이렇게 최악의 경우 O(n^2)이 됩니다. 피벗을 무작위로 고르면 이런 일이 일어날 가능성이 매우 낮아져 기대 시간이 O(n)이 됩니다.

import random

def quickselect(a, k):
    """a 에서 k 번째(0부터)로 작은 원소. a 의 순서를 제자리에서 바꾼다."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = random.randint(lo, hi)        # 무작위 피벗
        a[p], a[hi] = a[hi], a[p]
        pivot, store = a[hi], lo
        for i in range(lo, hi):           # 로무토 분할
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        if k == store:
            return a[k]
        if k < store:
            hi = store - 1
        else:
            lo = store + 1
    return a[k]

print(quickselect([7, 2, 9, 4, 1, 8, 3], 3))  # 4

정리

• 병합 정렬의 실제 작업은 병합에 있습니다. O(n) 작업이 log n 단계 반복됩니다.
• 오른쪽 원소가 먼저 꺼내질 때마다 len(left) - i만큼 경계를 넘는 역순 쌍이 생깁니다.
• 빠른 거듭제곱은 지수를 절반씩 줄여 곱셈을 O(log e)번만 합니다.
• 퀵셀렉트는 한쪽에서만 계속하며, 무작위 피벗으로 기대 시간 O(n)을 얻습니다.