동작 원리

이 장에서는 작은 배열을 손으로 따라가며 대표적인 정렬 알고리즘이 어떻게 움직이는지 봅니다. 단순한 정렬 세 가지를 짧게 훑은 뒤, 실무와 시험에 가장 많이 나오는 병합 정렬, 퀵 정렬, 힙 정렬, 그리고 비교하지 않는 계수 정렬을 차례로 추적합니다.

단순한 정렬 세 가지

• 버블 정렬: 이웃한 두 원소를 비교해 순서가 틀리면 바꿉니다. 한 바퀴 돌 때마다 가장 큰 값이 맨 뒤로 "떠오릅니다". 한 바퀴 동안 교환이 없으면 멈출 수 있습니다.
• 선택 정렬: 남은 구간에서 가장 작은 값을 찾아 맨 앞과 바꿉니다. 교환 횟수는 최대 n - 1번으로 적지만 비교는 항상 약 n²/2번입니다.
• 삽입 정렬: 앞쪽의 정렬된 구간에 다음 원소를 알맞은 자리에 끼워 넣습니다. 카드 패를 정리하는 방식과 같습니다.

세 가지 모두 평균 O(n²)이지만, 삽입 정렬은 거의 정렬된 입력에서 O(n)에 가깝게 끝나고 작은 배열에서 매우 빠르기 때문에 실제 라이브러리 정렬 안에서 작은 구간을 처리하는 부품으로 쓰입니다. [6, 3, 8, 2, 5]를 삽입 정렬로 따라가 봅니다.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:  # 더 큰 값만 오른쪽으로 민다 → 안정 정렬
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([6, 3, 8, 2, 5]))  # [2, 3, 5, 6, 8]

병합 정렬: 나누고 합치기

병합 정렬은 분할 정복의 대표 예입니다. 배열을 반으로 나누어 각각 재귀로 정렬한 다음, 정렬된 두 절반을 하나로 합칩니다. 합치기(merge)는 두 목록의 맨 앞을 비교해 작은 쪽을 꺼내는 일을 반복하는 것이고, 길이에 비례하는 시간이 듭니다. [38, 27, 43, 3, 9, 82, 10]을 정렬해 봅니다.

마지막 합치기에서는 두 목록의 맨 앞 27과 3을 비교해 3을 꺼내고, 이어서 27과 9, 27과 10, 27과 82를 비교하는 식으로 진행합니다. 값이 같을 때 왼쪽 것을 먼저 꺼내면 안정 정렬이 됩니다. 나누는 깊이는 log n, 각 깊이에서 합치는 일은 모두 합쳐 n이므로 전체는 O(n log n)입니다.

퀵 정렬: 기준값으로 가르기

퀵 정렬은 기준값(pivot)을 하나 골라 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 보내는 분할(partition)을 한 뒤, 양쪽을 재귀로 정렬합니다. 병합 정렬과 달리 합치는 단계가 없고, 추가 배열 없이 제자리에서 동작합니다. 가장 단순한 로무토(Lomuto) 분할로 [5, 2, 8, 1, 9, 3]을 기준값 3(마지막 원소)으로 나누어 봅니다. i는 "작은 값이 들어갈 다음 자리"입니다.

이제 3은 최종 자리(인덱스 2)에 있고, 왼쪽 [2, 1]과 오른쪽 [5, 9, 8]을 각각 같은 방법으로 정렬하면 끝납니다.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

data = [5, 2, 8, 1, 9, 3]
print(partition(data, 0, len(data) - 1), data)  # 2 [2, 1, 3, 5, 9, 8]

기준값이 매번 한쪽 끝 값이 되면(예: 이미 정렬된 배열에서 마지막 원소를 고를 때) 분할이 n - 1과 0으로 갈라져 O(n²)이 됩니다. 그래서 실제 구현은 기준값을 무작위로 고르거나 세 값의 중앙값을 씁니다.

힙 정렬: 최대 힙에서 하나씩 꺼내기

힙 정렬은 배열을 최대 힙(부모가 자식보다 크거나 같은 완전 이진 트리)으로 만든 뒤, 루트(최댓값)를 맨 뒤로 보내고 남은 부분을 다시 힙으로 고치는 일을 반복합니다. 인덱스 i의 자식은 2i + 1, 2i + 2입니다. [4, 10, 3, 5, 1]은 힙으로 만들면 [10, 5, 3, 4, 1]이 되고, 이후 과정은 다음과 같습니다.

힙 정렬은 최악에도 O(n log n)이고 추가 메모리가 O(1)이지만, 안정 정렬이 아니고 메모리 접근이 흩어져 있어 실제로는 퀵 정렬보다 느린 경우가 많습니다.

계수 정렬: 세어서 놓기

값이 0부터 k - 1 사이의 정수라면 비교 없이 정렬할 수 있습니다. 각 값이 몇 번 나오는지 세고, 누적 합으로 각 값이 들어갈 마지막 자리를 구한 다음, 입력을 뒤에서부터 훑으며 제자리에 놓습니다. 뒤에서부터 놓기 때문에 안정 정렬이 되고, 이 성질 덕분에 기수 정렬의 부품으로 쓸 수 있습니다.

def counting_sort(a, k):
    count = [0] * k
    for x in a:
        count[x] += 1
    for v in range(1, k):
        count[v] += count[v - 1]  # 누적 합: 값 v가 끝나는 위치 + 1
    out = [0] * len(a)
    for x in reversed(a):
        count[x] -= 1
        out[count[x]] = x
    return out

print(counting_sort([3, 1, 2, 3, 0, 1], 4))  # [0, 1, 1, 2, 3, 3]

기수 정렬은 이 계수 정렬을 낮은 자릿수부터 높은 자릿수까지 차례로 적용합니다. 각 단계가 안정적이므로 앞 단계에서 만든 순서가 깨지지 않습니다.

정리

• 삽입 정렬은 작은 배열과 거의 정렬된 배열에 강해 큰 정렬 알고리즘의 부품으로 쓰입니다.
• 병합 정렬은 나누고 합치며, 합칠 때 같은 값은 왼쪽을 먼저 꺼내 안정성을 지킵니다.
• 퀵 정렬은 기준값으로 분할하며, 기준값 선택이 성능을 좌우합니다.
• 힙 정렬은 최악에도 O(n log n)인 제자리 정렬이고, 계수 정렬은 값을 세어 비교 없이 정렬합니다.