삽입 정렬과 이미 정렬된 앞부분

카드 게임을 할 때 손에 든 카드를 정렬해 두는 사람이 많습니다. 새 카드를 한 장 받으면 처음부터 다시 정렬하지 않고, 이미 정렬된 카드 사이에서 알맞은 자리를 찾아 끼워 넣습니다. 이 방법을 그대로 옮긴 것이 삽입 정렬(insertion sort)입니다. 버블·선택 정렬과 마찬가지로 최악의 경우 Θ(n²)이지만 거의 정렬된 입력에서는 매우 빠르게 끝나서, 실제 정렬 라이브러리에서도 짧은 구간을 정렬할 때 쓰입니다. 이 글에서는 삽입 정렬을 만들고, 정렬된 앞부분을 어떻게 유지하는지, 값을 밀기 전에 왜 따로 저장해야 하는지, 입력에 따라 비용이 어떻게 달라지는지를 차례로 봅니다.

앞부분을 정렬된 채로 늘려 간다

삽입 정렬은 리스트를 두 부분으로 나누어 생각합니다. 왼쪽은 이미 정렬된 앞부분이고, 오른쪽은 아직 처리하지 않은 나머지입니다. 처음에는 첫 원소 하나만 앞부분에 넣는데, 원소가 하나뿐인 리스트는 언제나 정렬되어 있기 때문입니다. 그다음부터는 나머지의 첫 원소를 앞부분의 알맞은 자리에 끼워 넣어 앞부분을 한 칸씩 늘리고, 앞부분이 리스트 전체가 되면 정렬이 끝납니다. [4, 2, 3, 1]이라면 다음과 같이 진행합니다.

버블 정렬과 선택 정렬은 한 차례가 끝날 때마다 값 하나의 최종 자리가 정해졌습니다. 삽입 정렬의 앞부분은 정렬되어 있을 뿐, 그 안의 값들이 최종 자리에 있는 것은 아닙니다. i = 3 단계에서 1이 들어오면서 앞부분의 2, 3, 4가 모두 한 칸씩 뒤로 밀린 것이 그 예입니다.

끼워 넣을 자리를 만드는 방법

새 값을 끼워 넣으려면 그보다 큰 값들을 한 칸씩 오른쪽으로 밀어 빈자리를 만들어야 합니다. 이때 순서가 중요합니다. 끼워 넣을 값 result[i]를 먼저 current라는 변수에 따로 저장하고, 앞부분의 오른쪽 끝에서부터 왼쪽으로 가면서 current보다 큰 값을 한 칸씩 오른쪽으로 옮깁니다. current보다 크지 않은 값을 만나거나 앞부분의 왼쪽 끝을 지나면 멈추고, 마지막으로 옮긴 값이 있던 빈자리에 current를 씁니다.

i = 2 단계에서 [2, 4, 3, 1]의 3을 끼워 넣는 과정을 따라가 보겠습니다. 그림은 이 단계에 관련된 앞의 세 칸만 보여 줍니다.

둘째 줄에서 4를 오른쪽으로 옮기면 2번 칸에 있던 3이 덮여 리스트 안에서는 사라집니다. 그래도 current에 저장해 두었으므로 마지막에 올바른 자리에 쓸 수 있습니다. 4가 두 칸에 겹쳐 보이는 것은 1번 칸이 곧 비워질 자리이기 때문이며, 마지막 줄에서 3으로 채워집니다. 이렇게 값을 한 칸씩 미는 것은 버블 정렬의 교환보다 일이 적습니다. 교환은 두 칸에 모두 써야 하지만, 밀기는 한 칸에만 쓰고 current는 마지막에 한 번만 쓰기 때문입니다.

코드로 옮기면 다음과 같습니다. j는 current와 비교할 칸의 위치이고, 값을 하나 밀 때마다 왼쪽으로 한 칸 갑니다. 반복이 끝났을 때 j + 1이 빈자리입니다.

def insertion_sort(values):
    result = list(values)
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0 and result[j] > current:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = current
    return result


print(insertion_sort([4, 2, 3, 1]))
print(insertion_sort([1, 2, 3]))
print(insertion_sort([2, 2, 1]))
print(insertion_sort([]))

[1, 2, 3, 4]
[1, 2, 3]
[1, 2, 2]
[]

네 입력 모두 오름차순으로 나옵니다. 이미 정렬된 [1, 2, 3]에서는 단계마다 result[j] > current가 처음부터 거짓이라 아무 값도 밀지 않고, 빈 리스트에서는 range(1, 0)이 비어 있어 바깥 반복을 한 번도 돌지 않습니다. 그래서 길이를 따로 확인하는 코드가 없어도 빈 결과가 그대로 나옵니다.

왼쪽 끝을 확인하는 조건

while j >= 0 and result[j] > current의 앞쪽 조건 j >= 0은 앞부분의 왼쪽 끝을 지났는지 확인합니다. current가 앞부분의 모든 값보다 작으면 j가 -1이 될 때까지 밀게 되는데, 이때 반복을 멈추지 않으면 result[-1]을 읽게 됩니다. Python의 and는 앞쪽 조건이 거짓이면 뒤쪽 조건을 계산하지 않으므로, j가 -1이 되는 순간 result[j]를 읽지 않고 반복을 끝냅니다.

이 조건을 빼 버리면 어떻게 될까요? Python에서 -1은 마지막 칸을 가리키므로 오류가 나지 않고, 리스트의 맨 끝 값과 엉뚱한 비교가 이어집니다.

def insertion_without_bound(values):
    result = list(values)
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while result[j] > current:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = current
    return result


print(insertion_without_bound([2, 1, 1, 3]))

[1, 1, 3, 2]

i = 1 단계에서 1을 끼울 때 2를 밀고 j가 -1이 되지만, 반복이 멈추지 않고 result[-1], 곧 맨 끝의 3과 비교합니다. 3이 1보다 크므로 3을 0번 칸에 옮겨 쓰고 j는 -2가 되며, 이번에는 1이 1보다 크지 않아 멈춘 뒤 current를 result[-1]인 맨 끝 칸에 씁니다. 이 단계가 끝나면 리스트는 [3, 2, 1, 1]이 되어 정렬된 앞부분이라는 전제가 이미 깨지고, 끝내 틀린 결과가 나옵니다. 입력에 따라서는 j가 계속 줄어 리스트 바깥의 음수 인덱스가 되면서 IndexError가 나기도 하지만, 이 예처럼 오류 없이 틀린 결과를 내는 경우가 더 위험합니다.

왜 정렬되는가

삽입 정렬의 정확성은 다음 불변조건으로 설명합니다. i번째 단계를 시작할 때, 앞부분 result[0:i]에는 원래 리스트의 처음 i개 값이 정렬된 순서로 들어 있습니다.

i = 1에서 시작할 때 앞부분은 원소 하나라서 이 조건이 성립합니다. 한 단계가 조건을 지키는 이유는 이렇습니다. 반복은 current보다 큰 값들만 오른쪽으로 한 칸씩 옮기므로 그 값들끼리의 순서는 그대로이고, 멈춘 자리 j의 값은 current보다 크지 않거나 j가 -1입니다. 그래서 j + 1에 current를 쓰면 왼쪽에는 current 이하의 값이, 오른쪽에는 current보다 큰 값이 정렬된 채로 놓여 길이 i + 1인 앞부분이 정렬됩니다. 마지막 단계가 끝나면 앞부분이 리스트 전체이므로 전체가 정렬됩니다.

값을 잃지 않는다는 것도 확인할 수 있습니다. 밀기는 값을 오른쪽 칸에 복사하므로, 한 단계 동안 덮이는 칸은 처음의 result[i]뿐이고 그 값은 current에 저장했다가 다시 씁니다. 안쪽 반복은 j가 줄어들다가 늦어도 -1에서 멈추고, 바깥 반복의 범위는 정해져 있으므로 함수는 늘 끝납니다.

거의 정렬된 입력에서 빠른 이유

앞 글에서처럼 비교와 밀기 횟수를 세어 역순 쌍의 개수와 견주어 보겠습니다. 비교 횟수를 세기 쉽도록 while 조건을 둘로 나누어, 비교한 뒤 current보다 크지 않으면 break로 반복을 빠져나오게 했습니다.

def insertion_counts(values):
    result = list(values)
    comparisons = shifts = 0
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if result[j] <= current:
                break
            result[j + 1] = result[j]
            shifts += 1
            j -= 1
        result[j + 1] = current
    return result, comparisons, shifts


def inversions(values):
    count = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] > values[j]:
                count += 1
    return count


for values in [[1, 2, 3, 4, 5, 6], [1, 2, 3, 5, 4, 6], [6, 5, 4, 3, 2, 1], [4, 2, 6, 1, 5, 3]]:
    _, c, s = insertion_counts(values)
    print(values, "비교", c, "밀기", s, "역순 쌍", inversions(values))

[1, 2, 3, 4, 5, 6] 비교 5 밀기 0 역순 쌍 0
[1, 2, 3, 5, 4, 6] 비교 6 밀기 1 역순 쌍 1
[6, 5, 4, 3, 2, 1] 비교 15 밀기 15 역순 쌍 15
[4, 2, 6, 1, 5, 3] 비교 11 밀기 8 역순 쌍 8

밀기 횟수가 역순 쌍의 개수와 늘 같습니다. current를 끼워 넣는 동안 밀리는 값은 current보다 앞에 있으면서 current보다 큰 값, 곧 current와 역순 쌍을 이루는 값이고, 밀기 한 번이 그런 쌍을 하나씩 해소하기 때문입니다. 비교 횟수는 밀기 횟수에 단계마다 멈추면서 하는 비교 한 번씩을 더한 정도이므로, 삽입 정렬의 비용은 대략 n에 역순 쌍의 개수를 더한 만큼입니다.

그래서 이미 정렬된 입력에서는 단계마다 비교 한 번으로 끝나 Θ(n)이고, 두 값의 자리만 바뀐 둘째 입력도 비교 6번이면 됩니다. 이처럼 입력이 정렬된 상태에 가까울수록 빨리 끝나는 성질을 적응형(adaptive)이라고 합니다. 넷째 입력은 앞 글에서 버블 정렬이 비교 14번과 교환 8번을 한 입력인데, 삽입 정렬은 비교 11번과 밀기 8번으로 끝났습니다. 바꾸는 횟수는 같은 역순 쌍 개수로 정해지지만, 비교가 더 적고 밀기 한 번이 교환 한 번보다 가볍습니다.

같은 키의 순서

삽입 정렬은 result[j] > current가 참일 때만 밉니다. 키가 같은 값은 밀지 않으므로 current는 같은 키를 가진 앞의 값을 지나쳐 그 앞으로 가지 않고, 원래 순서대로 그 뒤에 놓입니다. 그래서 삽입 정렬은 안정 정렬입니다. 키만 비교하도록 바꾸어 확인해 보겠습니다.

def insertion_by_key(records):
    result = list(records)
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0 and result[j][0] > current[0]:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = current
    return result


print(insertion_by_key([(2, "가"), (1, "나"), (2, "다"), (1, "라")]))

[(1, '나'), (1, '라'), (2, '가'), (2, '다')]

키가 1인 "나"와 "라", 키가 2인 "가"와 "다"가 모두 입력의 순서를 그대로 지켰습니다. 조건을 >=로 바꾸면 같은 키의 값도 밀게 되어 이 성질이 깨집니다.

비용과 쓰임

최선의 경우인 정렬된 입력에서는 Θ(n), 최악의 경우인 역순 입력에서는 비교와 밀기가 모두 n(n - 1)/2번이라 Θ(n²)입니다. 값이 모두 다른 무작위 순서에서는 역순 쌍이 평균 n(n - 1)/4개이므로 평균도 Θ(n²)입니다. 추가 공간은 current와 j 같은 변수 몇 개뿐인 O(1)이고, 이 글의 함수는 원본을 남기려는 복사 때문에 O(n)을 더 씁니다.

큰 무작위 입력에는 맞지 않지만, 원소가 수십 개 정도로 적거나 거의 정렬된 입력에서는 반복이 단순한 덕분에 더 복잡한 정렬보다 빠를 때가 많습니다. CPython의 내장 정렬도 짧은 구간은 삽입 정렬의 변형으로 정렬한 뒤 그 구간들을 합칩니다. 또 삽입 정렬은 값이 하나씩 도착하는 상황에서도 그때마다 정렬된 상태를 유지할 수 있어서, 입력 전체를 미리 갖고 있지 않아도 쓸 수 있습니다.

더 깊이: 자리를 이진 탐색으로 찾으면

앞부분은 정렬되어 있으므로, current가 들어갈 자리를 하나씩 비교하며 찾는 대신 이진 탐색으로 찾을 수도 있습니다. 이것을 이진 삽입 정렬(binary insertion sort)이라고 합니다. Python의 bisect.insort는 정렬된 리스트에 값을 끼워 넣을 자리를 이진 탐색으로 찾아 넣는 함수라서, 이것을 되풀이하면 이진 삽입 정렬이 됩니다.

from bisect import insort


def binary_insertion_sort(values):
    result = []
    for value in values:
        insort(result, value)
    return result


print(binary_insertion_sort([4, 2, 3, 1]))

[1, 2, 3, 4]

비교 횟수는 단계마다 O(log n)이라 전체 O(n log n)으로 줄어듭니다. 하지만 자리를 찾은 뒤 그 뒤의 값들을 한 칸씩 옮기는 일은 그대로라서, 역순 입력에서는 여전히 Θ(n²)번을 옮깁니다. 비교가 옮기기보다 훨씬 비싼 값을 정렬할 때 이득이 큰 방법입니다. insort는 같은 값이 이미 있으면 그 뒤에 넣으므로 이 방법도 안정 정렬입니다.

정리

• 삽입 정렬은 정렬된 앞부분에 다음 값을 알맞은 자리에 끼워 넣어 앞부분을 한 칸씩 늘립니다.
• 끼워 넣을 값을 current에 먼저 저장해야 큰 값을 오른쪽으로 밀면서 덮어써도 값을 잃지 않습니다.
• j >= 0 조건이 없으면 Python의 음수 인덱스 때문에 오류 없이 틀린 결과가 나올 수 있습니다.
• 밀기 횟수는 역순 쌍의 개수와 같아서, 비용이 대략 n과 역순 쌍 개수의 합입니다. 정렬된 입력에서는 Θ(n), 최악과 평균은 Θ(n²)입니다.
• 키가 같은 값은 밀지 않으므로 삽입 정렬은 안정 정렬입니다.

연습 문제

1. 단계마다 리스트 쓰기

[3, 1, 2]를 삽입 정렬할 때 각 i 단계가 끝난 뒤의 리스트를 쓰고, 밀기 횟수를 구하세요.

2. current를 저장하지 않으면

current에 저장하지 않고 result[i]를 직접 비교하고 써 넣으면 [4, 2, 3, 1]의 결과가 어떻게 될까요?

def insertion_without_current(values):
    result = list(values)
    for i in range(1, len(result)):
        j = i - 1
        while j >= 0 and result[j] > result[i]:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = result[i]
    return result


print(insertion_without_current([4, 2, 3, 1]))

[4, 4, 4, 4]

3. 밀기 횟수 예측하기

[2, 1, 4, 3, 6, 5]를 삽입 정렬하면 밀기는 몇 번 일어날까요? 정렬을 직접 하지 않고 역순 쌍만 세어 답해 보세요.

다음 글 정렬의 정답 조건·안정성·시간 측정에서는 지금까지 만든 세 정렬이 정말 맞는지 검사하는 방법과, 실행 시간을 재서 비교할 때 주의할 점을 다룹니다.