정렬의 정답 조건·안정성·시간 측정

버블·선택 정렬과 삽입 정렬을 만들면서 몇 가지 입력으로 결과를 확인했습니다. 하지만 손으로 고른 입력 몇 개에서 맞았다고 모든 입력에서 맞는다고 말할 수는 없습니다. 또 세 정렬 가운데 어느 것이 빠른지도 증가율만으로는 다 알 수 없어서, 실제로 재 보아야 할 때가 있습니다. 이 글에서는 정렬 결과가 맞는다는 것이 정확히 무엇인지 정하고, 그 조건을 코드로 검사하는 방법, 같은 키의 순서를 확인하는 방법, 실행 시간을 믿을 만하게 재는 방법을 차례로 다룹니다.

정렬 결과가 맞으려면 두 조건이 필요하다

정렬 결과가 맞으려면 두 가지가 함께 성립해야 합니다. 첫째, 결과가 비내림차순이어야 합니다. 둘째, 결과에 든 값들이 입력의 값들과 같아야 합니다. 값의 종류뿐 아니라 각 값이 나오는 횟수까지 같아야 한다는 뜻입니다. 둘 중 하나만 확인하면 틀린 결과를 놓칩니다. [1, 1, 2]를 정렬해 [1, 2]를 내놓는 함수는 순서는 맞지만 1을 하나 잃었고, [2, 1, 1]을 내놓는 함수는 값은 다 있지만 순서가 틀렸습니다.

from collections import Counter


def is_sorted(values):
    return all(values[i] <= values[i + 1] for i in range(len(values) - 1))


def same_values(a, b):
    return Counter(a) == Counter(b)


source = [1, 1, 2]
for result in [[1, 1, 2], [1, 2], [2, 1, 1]]:
    print(result, is_sorted(result), same_values(source, result))

[1, 1, 2] True True
[1, 2] True False
[2, 1, 1] False True

is_sorted는 이웃한 모든 쌍이 순서대로인지 확인합니다. all(...)은 괄호 안의 조건이 모두 참일 때만 참을 돌려줍니다. Counter는 값마다 몇 번 나오는지를 세어 딕셔너리처럼 담는 표준 라이브러리 도구라서, 두 Counter가 같으면 값과 횟수가 모두 같습니다. 세 결과 가운데 두 조건을 모두 통과한 것은 첫 번째뿐입니다.

실제 검사에서는 두 조건을 따로 확인하는 대신, 같은 입력을 Python의 sorted로 정렬한 결과와 비교하는 방법을 자주 씁니다. sorted는 충분히 검증된 정렬이므로, 우리 함수의 결과가 그것과 리스트로서 같다면 순서와 값의 횟수가 모두 맞습니다. 이렇게 정답을 내 줄 믿을 만한 구현을 기준 구현(reference implementation)이라고 합니다.

원본을 바꾸는지도 확인한다

정렬 함수에는 입력을 그대로 두고 새 리스트를 돌려주는 방식과, 입력 리스트 자체를 바꾸는 방식이 있습니다. Python에서도 sorted(values)는 새 리스트를 돌려주고, values.sort()는 values를 그 자리에서 정렬합니다. 그 자리에서 정렬하는 쪽은 결과를 따로 돌려주지 않고 None을 돌려주므로, values = values.sort()처럼 쓰면 정렬된 리스트 대신 None이 남습니다.

values = [3, 1, 2]
result = sorted(values)
print(result, values)
values.sort()
print(values)
wrong = values.sort()
print(wrong)

[1, 2, 3] [3, 1, 2]
[1, 2, 3]
None

추가 공간을 거의 쓰지 않고 입력 안에서 값을 옮겨 정렬하는 것을 제자리 정렬(in-place sorting)이라고 합니다. 세 기본 정렬은 본래 제자리 정렬이지만, 이 교재의 함수들은 원본을 남기려고 처음에 복사본을 만들었습니다. 원본을 바꾸지 않겠다고 정한 함수라면, 검사할 때 실행 뒤에 입력이 정말 그대로인지도 확인해야 합니다.

어떤 입력으로 검사할까

검사 입력은 흔히 저지르는 실수가 드러나도록 고릅니다. 다음은 정렬을 검사할 때 꼭 넣는 입력과, 각 입력이 잘 찾아내는 실수입니다.

이런 입력을 직접 고르는 것과 함께, 무작위 입력을 많이 만들어 기준 구현과 비교하는 방법도 씁니다. 이것을 무작위 검사(randomized testing)라고 합니다. 사람이 미처 떠올리지 못한 입력의 조합을 시험해 볼 수 있다는 것이 장점입니다. 값의 범위를 0부터 5 정도로 좁게 잡으면 같은 값이 자주 나와서 중복과 관련된 실수도 잘 드러납니다. 난수 생성기에 시드(seed)를 정해 두면 실행할 때마다 같은 입력이 만들어지므로, 실패한 입력을 다시 만들어 고치기도 쉽습니다.

세 정렬을 한꺼번에 검사하기

아래 코드는 앞의 두 글에서 만든 세 정렬을 다시 정의하되, 정렬 기준을 정하는 key 매개변수를 받도록 고쳤습니다. key=lambda value: value는 값을 그대로 돌려주는 짧은 함수를 기본값으로 둔다는 뜻이라서, key를 주지 않으면 값 자체를 비교합니다. lambda record: record[0]처럼 다른 함수를 주면 그 함수가 돌려주는 값으로 비교합니다.

check는 결과가 기준 구현과 같은지, 원본이 그대로인지를 assert로 확인합니다. 조건이 거짓이면 쉼표 뒤의 값이 오류 메시지에 함께 나오므로, 어떤 입력에서 실패했는지 바로 알 수 있습니다. is_stable은 같은 키를 가진 값들의 순서를 검사하는데, 이것은 다음 절에서 설명합니다.

import random


def bubble_sort(values, key=lambda value: value):
    result = list(values)
    for end in range(len(result) - 1, 0, -1):
        changed = False
        for i in range(end):
            if key(result[i]) > key(result[i + 1]):
                result[i], result[i + 1] = result[i + 1], result[i]
                changed = True
        if not changed:
            break
    return result


def selection_sort(values, key=lambda value: value):
    result = list(values)
    for i in range(len(result) - 1):
        smallest = i
        for j in range(i + 1, len(result)):
            if key(result[j]) < key(result[smallest]):
                smallest = j
        if smallest != i:
            result[i], result[smallest] = result[smallest], result[i]
    return result


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


def check(sort_function, values):
    before = list(values)
    result = sort_function(values)
    assert result == sorted(before), (sort_function.__name__, before, result)
    assert values == before, (sort_function.__name__, "원본이 바뀌었다", before)


def is_stable(sort_function, keys):
    records = [(k, index) for index, k in enumerate(keys)]
    result = sort_function(records, key=lambda record: record[0])
    return result == sorted(records, key=lambda record: record[0])


edge_cases = [[], [5], [2, 2, 2], [1, 2, 3, 4], [4, 3, 2, 1], [3, 1, 3, 2]]
rng = random.Random(2026)
random_cases = [[rng.randint(0, 5) for _ in range(rng.randint(0, 12))] for _ in range(1000)]

for sort_function in [bubble_sort, selection_sort, insertion_sort]:
    for values in edge_cases + random_cases:
        check(sort_function, values)
    stable = all(is_stable(sort_function, keys) for keys in random_cases)
    print(f"{sort_function.__name__}: {len(edge_cases) + len(random_cases)}개 통과, 안정 정렬 {stable}")

bubble_sort: 1006개 통과, 안정 정렬 True
selection_sort: 1006개 통과, 안정 정렬 False
insertion_sort: 1006개 통과, 안정 정렬 True

random.Random(2026)은 시드 2026으로 난수 생성기를 만들고, rng.randint(0, 12)는 0 이상 12 이하의 정수를 하나 고릅니다. 그래서 random_cases는 길이가 0부터 12까지이고 값이 0부터 5까지인 리스트 1000개입니다. 세 정렬 모두 경계 사례 6개와 무작위 입력 1000개를 합한 1006개 입력에서 기준 구현과 같은 결과를 냈고, 원본도 바꾸지 않았습니다.

검사를 통과했다는 것은 이 1006개 입력에서 틀린 결과가 나오지 않았다는 뜻일 뿐, 모든 입력에서 맞는다는 증명은 아닙니다. 모든 입력에서 맞는 이유는 앞의 두 글에서 불변조건으로 설명했습니다. 검사와 증명은 서로를 대신하지 않고 함께 씁니다. 증명은 생각한 알고리즘이 맞는지를 보여 주고, 검사는 그 알고리즘을 코드로 옮기면서 생긴 실수를 찾아 줍니다.

안정성을 검사하는 방법

is_stable은 키 목록의 각 값에 원래 위치를 붙여 (키, 위치) 튜플을 만든 뒤 키만 비교해 정렬합니다. 안정 정렬이라면 키가 같은 튜플끼리는 원래 위치가 작은 것이 앞에 와야 합니다. Python의 sorted는 안정 정렬이라고 문서에 정해져 있으므로, key를 준 sorted의 결과가 곧 안정 정렬의 정답이 됩니다. 우리 함수의 결과가 이것과 같으면 이 입력에서는 같은 키의 순서를 지킨 것입니다.

출력에서 선택 정렬만 안정 정렬이 아니라고 나왔습니다. 무작위 입력 1000개 가운데 400개 남짓에서 순서가 뒤집혔습니다. 가장 작은 예는 키 목록 [2, 2, 1]입니다. 튜플로는 [(2, 0), (2, 1), (1, 2)]이고, 선택 정렬은 첫 차례에 (2, 0)과 (1, 2)를 맞바꾸어 [(1, 2), (2, 1), (2, 0)]을 만듭니다. 키가 2인 두 튜플의 위치 표시가 1, 0 순서가 되어 원래 순서와 반대입니다.

안정성이 쓸모 있는 곳

안정성은 여러 기준으로 정렬할 때 특히 쓸모가 있습니다. 학생 기록을 반 순서로 늘어놓되, 같은 반 안에서는 점수가 높은 순서로 늘어놓고 싶다고 해 봅시다. 안정 정렬을 쓰면 덜 중요한 기준으로 먼저 정렬하고, 그 결과를 더 중요한 기준으로 다시 정렬하면 됩니다. 두 번째 정렬에서 반이 같은 학생들은 첫 번째 정렬에서 만든 점수 순서를 그대로 유지하기 때문입니다.

students = [("민수", 2, 85), ("지수", 1, 92), ("하늘", 2, 92), ("보라", 1, 85), ("다온", 2, 78)]
by_score = sorted(students, key=lambda student: student[2], reverse=True)
by_class = sorted(by_score, key=lambda student: student[1])
for student in by_class:
    print(student)

('지수', 1, 92)
('보라', 1, 85)
('하늘', 2, 92)
('민수', 2, 85)
('다온', 2, 78)

첫 번째 sorted는 점수가 높은 순서로 정렬합니다. reverse=True는 큰 것부터 늘어놓으라는 뜻이며, Python 문서에 따르면 이렇게 거꾸로 정렬할 때도 같은 키의 원래 순서는 유지됩니다. 두 번째 sorted는 반으로 정렬하는데, 안정 정렬이라서 1반의 지수와 보라, 2반의 하늘, 민수, 다온이 점수 순서를 그대로 지킵니다. key=lambda student: (student[1], -student[2])처럼 반과 점수를 묶은 튜플을 키로 주면 한 번의 정렬로 같은 결과를 얻을 수도 있습니다. 여러 기준의 정렬은 공식 문서의 Sorting Techniques에 더 많은 예가 있습니다.

실행 시간 재기

증가율은 입력이 커질 때 비용이 늘어나는 모양을 알려 주지만, 실제로 몇 초가 걸리는지는 알려 주지 않습니다. 그래서 실행 시간을 직접 재 보기도 하는데, 잴 때는 몇 가지를 지켜야 믿을 만한 숫자가 나옵니다.

• 비교하는 함수들에 같은 입력을 줍니다. 입력을 만드는 시간은 재는 구간에 넣지 않습니다.
• 같은 측정을 여러 번 하고 가장 짧은 시간을 씁니다. 다른 프로그램이 끼어들면 시간이 길어질 수는 있어도 짧아지지는 않으므로, 가장 짧은 시간이 그 코드 자체의 속도에 가장 가깝습니다. Python의 timeit 문서도 결과의 최솟값을 보라고 권합니다.
• 입력 크기를 두 배씩 늘려 가며 잽니다. 크기 하나에서 잰 시간만으로는 증가율을 알 수 없지만, 두 배로 늘렸을 때 시간이 몇 배가 되는지는 증가율을 짐작하게 해 줍니다.

import random
import timeit


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


rng = random.Random(2026)
for n in [500, 1000, 2000]:
    values = [rng.randrange(1_000_000) for _ in range(n)]
    t_insertion = min(timeit.repeat(lambda: insertion_sort(values), number=3, repeat=5)) / 3
    t_sorted = min(timeit.repeat(lambda: sorted(values), number=300, repeat=5)) / 300
    print(f"n={n:5}  삽입 정렬 {t_insertion * 1000:7.2f} ms  sorted {t_sorted * 1000:7.3f} ms")

timeit.repeat(함수, number=3, repeat=5)는 함수를 3번 실행하는 데 걸린 시간을 5번 재어 리스트로 돌려줍니다. 그 최솟값을 3으로 나누면 한 번 실행하는 데 걸린 시간입니다. sorted는 너무 빨라서 한 번만 재면 시간이 너무 짧게 나오므로 300번씩 묶어 잽니다.

실행 결과는 컴퓨터와 실행할 때마다 달라서 여기에 그대로 싣지 않습니다. 이 글을 쓰며 한 컴퓨터에서 실행했을 때 삽입 정렬은 n이 500, 1000, 2000일 때 약 2.6, 9.9, 40.6밀리초가 걸려 n이 두 배가 될 때마다 약 4배로 늘었습니다. 비용이 n²에 비례하면 n이 두 배일 때 4배가 되므로 이론과 잘 맞습니다. 같은 입력에서 sorted는 세 크기 모두 0.11밀리초 이하로, 삽입 정렬보다 수백 배 빨랐습니다. sorted는 시간이 워낙 짧아 이 크기에서는 늘어나는 비율이 고르지 않았는데, n을 수천에서 십수만까지 키워 재 보니 두 배마다 약 2.2배씩 늘어 n log n의 증가율에 가까웠습니다.

sorted가 이렇게 빠른 데는 두 가지 이유가 있습니다. 하나는 n log n 규모의 알고리즘이라는 점이고, 다른 하나는 C로 구현되어 같은 일을 해도 Python 반복문보다 훨씬 빠르다는 점입니다. 측정 결과에는 알고리즘의 차이와 구현의 차이가 섞여 있으므로, 두 정렬의 알고리즘을 비교하고 싶다면 같은 언어와 같은 방식으로 구현한 것끼리 재야 합니다.

세 기본 정렬 한눈에 보기

세 정렬은 모두 추가 공간이 O(1)인 제자리 정렬로 만들 수 있고, 이 교재의 함수는 원본을 남기려는 복사 때문에 O(n)을 더 씁니다. 작은 입력이나 거의 정렬된 입력에서는 삽입 정렬이 셋 가운데 가장 나은 선택인 경우가 많습니다. 하지만 큰 무작위 입력에서는 셋 모두 Θ(n²)이라 금세 느려집니다. 비교만으로 정렬하는 방법은 최악의 경우 약 log₂(n!)번, 곧 n log₂ n 규모보다 적게 비교할 수 없다는 것을 입력 크기·O·Ω·Θ와 정보의 개수에서 보았습니다. 5장의 병합 정렬과 6장의 힙 정렬은 최악의 경우에도 이 하한에 맞는 O(n log n)을 달성합니다.

정리

• 정렬 결과가 맞으려면 비내림차순이어야 하고, 값과 각 값의 개수가 입력과 같아야 합니다. 기준 구현 sorted의 결과와 비교하면 두 조건을 한 번에 확인할 수 있습니다.
• sorted는 새 리스트를 돌려주고 list.sort()는 그 자리에서 정렬한 뒤 None을 돌려줍니다. 원본을 바꾸지 않는 함수라면 그것도 검사합니다.
• 빈 리스트, 원소 하나, 같은 값, 정렬된 입력, 역순 입력, 중복이 섞인 입력을 경계 사례로 넣고, 시드를 정한 무작위 입력으로 많이 검사합니다. 검사 통과는 증명을 대신하지 않습니다.
• 안정성은 값에 원래 위치를 붙여 정렬해 보면 검사할 수 있고, 덜 중요한 기준부터 차례로 정렬하는 여러 기준 정렬에 쓰입니다.
• 실행 시간은 같은 입력으로 여러 번 재어 최솟값을 쓰고, 입력 크기를 두 배씩 늘려 가며 증가율을 확인합니다. 측정에는 알고리즘과 구현의 차이가 함께 섞여 있습니다.

연습 문제

1. 검사 입력이 잡아내는 실수

삽입 정렬의 while j >= 0 and ...를 while j > 0 and ...로 잘못 썼습니다. 본문의 경계 사례 가운데 어떤 입력이 이 실수를 잡아낼까요? 이 실수를 드러내는 가장 짧은 입력도 생각해 보세요.

2. 입력을 10배로 늘리면

크기 n인 입력에서 1초가 걸리는 세 프로그램이 있습니다. 비용이 각각 n, n², n log₂ n에 비례한다면, n = 1000에서 입력을 10배로 늘렸을 때 대략 몇 초가 걸릴까요?

3. 제자리 정렬을 여러 번 재면

timeit.repeat(lambda: values.sort(), number=5, repeat=5)처럼 같은 리스트에 values.sort()를 되풀이해 재면, sorted(values)를 잰 것보다 훨씬 빠르게 나옵니다. 왜 그럴까요?

다음 장의 재귀·기저 사례·호출 스택에서는 문제를 같은 모양의 작은 문제로 나누어 푸는 재귀를 익히고, 이를 바탕으로 n log n 규모의 정렬을 만듭니다.