정렬 - 원리와 활용
이 장에서 배우는 것
정렬은 데이터를 일정한 기준에 따라 늘어놓는 일이다. 숫자를 작은 순서로 나열하는 데서 출발하지만, 실제 목적은 순서를 만든 다음 필요한 답을 쉽게 찾는 데 있다. 접수 목록을 처리 순서대로 배치하거나, 기록 사이의 가장 작은 차이를 구하는 일이 그 예다.
앞 장에서 큰 문제를 작은 문제로 나누고 다시 결합하는 방법을 살펴보았다. 이번에는 그 생각을 병합 정렬에 적용한다. 선택·삽입·퀵 정렬도 함께 비교하면서, 각 알고리즘이 실행 도중 어떤 사실을 계속 유지하는지 확인한다. 이러한 사실을 불변식(invariant)이라고 한다.
- 선택·삽입·병합·퀵 정렬의 불변식을 말로 설명한다.
- 안정 정렬(stable sort)이 같은 기준값을 가진 기록에 어떤 영향을 주는지 확인한다.
- 키 함수(key function)와 여러 정렬 기준을 사용해 처리 순서를 만든다.
- 정렬한 뒤 이웃한 값만 살펴봐도 되는 문제의 근거를 설명한다.
- 직접 작성한 정렬을 작은 입력 전체와 고정된 난수 입력으로 검증한다.
문제 상황
작은 작업실에서 수선 물품을 접수한다고 하자. 담당자는 접수 기록마다 식별자, 우선등급, 예상 작업 시간을 남긴다. 우선등급은 숫자가 작을수록 먼저 처리한다. 등급이 같으면 예상 작업 시간이 짧은 기록을 먼저 처리하고, 두 값이 모두 같으면 먼저 접수한 기록을 앞에 둔다.
첫 번째 문제는 이 규칙으로 접수 목록을 정렬하는 일이다. 식별자는 출력을 위한 이름일 뿐 정렬 기준은 아니다. 이름까지 비교하면 접수 순서를 보존해야 한다는 조건이 달라질 수 있다.
두 번째 문제는 포장대에 남은 자재 길이를 점검하는 일이다. 서로 다른 두 자재의 길이 차이가 가장 작은 값을 구한다. 길이가 같은 자재가 두 개라면 답은 0이다. 입력에 자재가 두 개 미만이면 비교할 쌍이 없으므로 답을 없음을 뜻하는 값으로 정한다.
세 번째 문제는 정렬 도구 자체를 검사하는 일이다. 직접 만든 병합 정렬이 빈 목록, 중복값, 이미 정렬된 목록에서도 올바르게 동작하는지 확인한다. 짧은 목록은 가능한 입력을 모두 만들고, 조금 더 긴 목록은 난수 생성기의 시작값을 고정해 검사한다.
| 문제 | 입력 | 필요한 결과 | 정렬의 역할 |
|---|---|---|---|
| 접수 순서 | 식별자·등급·시간 | 처리할 기록의 순서 | 여러 기준을 하나의 순서로 만든다 |
| 자재 길이 | 자재 길이 목록 | 두 길이의 최소 차이 | 검사할 쌍을 이웃으로 줄인다 |
| 정렬 검증 | 정수와 접수 기록 | 정답과의 일치 여부 | 순서와 동률 처리를 확인한다 |
정렬 중에도 유지되는 사실
정렬 결과에는 두 조건이 필요하다. 첫째, 앞의 값이 뒤의 값보다 크지 않아야 한다. 둘째, 입력에 있던 원소가 개수까지 그대로 남아 있어야 한다. 예를 들어 [1, 1, 3]을 [1, 3]으로 바꾸면 순서는 맞지만 정렬 결과는 아니다. 아래 알고리즘들은 원소를 교환하거나 옮겨 담으므로 두 번째 조건도 함께 추적할 수 있다.
선택 정렬: 앞부분의 자리를 확정한다
선택 정렬(selection sort)은 아직 처리하지 않은 부분에서 가장 작은 원소를 골라 그 부분의 맨 앞과 교환한다. 입력 [5, 2, 4, 1]을 손으로 따라가 보자. 표의 경계 왼쪽은 자리가 확정된 부분이다.
| 단계 | 선택한 값 | 교환 후 목록 | 확정된 부분 |
|---|---|---|---|
| 시작 | 없음 | 5, 2, 4, 1 | 없음 |
| 첫 자리 | 1 | 1 | 2, 4, 5 | 1 |
| 둘째 자리 | 2 | 1, 2 | 4, 5 | 1, 2 |
| 셋째 자리 | 4 | 1, 2, 4 | 5 | 1, 2, 4 |
반복 시작 시 앞의 i개 원소는 전체에서 작은 i개를 오름차순으로 담고 있으며, 남은 값보다 크지 않다. 이것이 불변식이다. 남은 부분의 최솟값을 i번 자리에 놓으면 같은 설명이 i + 1개에 대해 성립한다. 마지막에는 모든 자리가 확정된다.
비교 횟수는 (n - 1) + (n - 2) + … + 1이므로 시간은 O(n²)이다. 교환에 필요한 추가 공간은 O(1)이다. 완성 코드에서는 호출자가 준 목록을 보존하려고 복사하므로 함수 전체의 추가 공간은 O(n)이다.
삽입 정렬: 정돈된 부분에 하나를 끼운다
삽입 정렬(insertion sort)은 앞부분을 정렬된 상태로 유지하면서 다음 원소를 알맞은 위치에 넣는다. [2, 5 | 4, 1]이라면 4를 따로 잡고, 4보다 큰 5를 오른쪽으로 민다. 빈자리에 4를 넣으면 [2, 4, 5 | 1]이 된다.
반복 시작 시 앞의 i개 원소는 원래 앞의 i개 원소를 정렬한 결과다. 다음 값을 넣을 때 그 값보다 큰 원소만 오른쪽으로 이동한다. 이동한 원소 사이의 순서는 바뀌지 않으며, 빈자리에 새 값을 넣으면 앞의 i + 1개가 정렬된다.
이동 중에는 따로 보관한 값과 목록을 함께 상태로 보아야 한다. 빈자리를 만들면서 목록 안에 같은 값이 잠시 두 번 보일 수 있지만, 보관한 값을 넣으면 원소의 개수가 다시 맞는다.
이미 정렬된 입력에서는 매번 바로 멈추므로 시간이 O(n)이다. 역순 입력에서는 앞부분을 계속 밀어야 하므로 O(n²)이다. 목록 자체를 수정하는 핵심 작업의 추가 공간은 O(1)이며, 아래처럼 복사본을 만들면 함수 전체는 O(n)이다.
병합 정렬과 퀵 정렬: 나누는 방식이 다르다
병합 정렬(merge sort)은 목록을 반으로 나누고, 각각 정렬한 뒤 두 결과를 합친다. 길이가 0이나 1이면 이미 정렬되어 있다. 두 정렬된 목록에서 아직 사용하지 않은 맨 앞 값 중 작은 것을 고르면 전체에서 다음으로 작은 값을 얻는다.
병합 반복의 불변식은 결과 목록에 지금까지 꺼낸 원소들이 정렬되어 있고, 그 원소들이 두 입력 전체에서 먼저 나와야 할 원소들이라는 것이다. 각 입력이 정렬되어 있으므로 남아 있는 최솟값은 두 맨 앞 값 중 하나다. 둘 중 작은 값을 붙여도 불변식이 유지된다. 한쪽이 끝나면 다른 쪽의 나머지를 그대로 붙일 수 있다.
길이가 더 짧은 입력에서 정렬이 올바르다고 가정하면, 재귀 호출의 두 결과는 정렬되어 있다. 병합의 불변식에 따라 합친 결과도 올바르다. 이것이 앞 장에서 다룬 귀납을 적용한 정확성 근거다. 반으로 나누는 단계가 O(log n)개이고 각 단계에서 전체 O(n)개를 다루므로 시간은 O(n log n)이다. 아래 구현의 동시에 살아 있는 목록 공간은 O(n), 재귀 호출 공간은 O(log n)이다.
퀵 정렬(quicksort)은 기준값을 먼저 정하고, 그 값 이하인 원소와 더 큰 원소로 구역을 나눈다. 아래 구현은 구간의 마지막 값을 기준값으로 잡는다. 검사 도중 왼쪽 경계 전까지는 기준값 이하, 경계부터 검사 위치 전까지는 기준값보다 큰 원소다. 아직 검사하지 않은 부분은 그 뒤에 남는다.
새 값이 기준값 이하이면 왼쪽 구역 끝으로 옮기고 경계를 늘린다. 검사가 끝나면 기준값을 경계에 놓는다. 이제 기준값 왼쪽에는 그 이하의 값만, 오른쪽에는 더 큰 값만 있다. 두 구역을 재귀적으로 정렬하면 전체도 정렬된다.
구역 크기가 균형 있게 나뉘면 시간은 O(n log n)이지만, 한쪽으로 몰리면 O(n²)이다. 이 구현은 정렬된 입력이나 같은 값이 많은 입력에서 한쪽으로 몰릴 수 있다. 재귀 공간도 균형이 맞으면 O(log n), 몰리면 O(n)이며 큰 입력에서는 재귀 깊이 제한에 걸릴 수 있다. 완성 코드의 퀵 정렬은 짧은 입력에서 원리를 확인하는 용도다.
같은 값의 순서와 여러 정렬 기준
정렬 기준값이 같은 원소들의 원래 순서를 보존하면 안정 정렬이다. 접수 기록에서 등급과 시간이 같은 두 건의 접수 순서를 지켜야 할 때 이 성질을 사용한다. 안정성은 전체 기록이 같은지를 따지는 성질이 아니라, 비교에 사용한 기준값이 같은 기록을 어떻게 다루는지에 관한 성질이다.
삽입 정렬에서 새 값보다 큰 원소만 밀면 같은 값은 밀리지 않는다. 따라서 새 값은 먼저 있던 동률 원소 뒤에 놓인다. 병합 정렬에서는 두 맨 앞 값이 같을 때 왼쪽 값을 먼저 꺼낸다. 왼쪽 부분은 원래 입력에서도 앞에 있었으므로 접수 순서를 유지할 수 있다.
선택 정렬과 아래 퀵 정렬은 안정적이지 않다. 값 2인 기록 A와 B, 값 1인 기록 C가 [A, B, C]로 들어왔다고 하자. 선택 정렬의 첫 교환으로 [C, B, A]가 된다. 값 2의 순서가 바뀐다. 마지막 원소를 기준으로 삼는 아래 퀵 정렬도 이 입력에서 같은 변화가 생긴다.
접수 기록을 (식별자, 등급, 시간)으로 나타내면 기준은 lambda row: (row[1], row[2])다. 튜플은 첫 항목을 먼저 비교하고, 같을 때 다음 항목을 비교한다. 식별자를 기준에 넣지 않으면 두 숫자가 같은 기록의 순서는 안정 정렬이 보존한다.
records = [("B", 2, 5), ("A", 1, 8), ("C", 2, 3), ("D", 2, 5)]
ordered = sorted(records, key=lambda row: (row[1], row[2]))Python의 sorted는 새 목록을 반환하고, 목록의 sort 메서드는 원본을 수정한 뒤 None을 반환한다. 두 기능 모두 안정 정렬을 제공한다. 기준값은 원소마다 한 번 계산되므로 문자열 가공처럼 비용이 드는 작업은 비교할 때마다 반복하기보다 키 함수에 담는 편이 좋다.
여러 번 나누어 정렬할 수도 있다. 이때 덜 중요한 기준부터 적용한다. 시간을 먼저 정렬하고 등급을 나중에 안정적으로 정렬하면, 같은 등급 안에서 앞서 만든 시간 순서가 유지된다.
ordered = sorted(records, key=lambda row: row[2])
ordered.sort(key=lambda row: row[1])등급은 오름차순, 시간은 내림차순처럼 방향이 다르고 기준값이 숫자라면 (row[1], -row[2])를 사용할 수 있다. reverse=True는 전체 기준의 방향을 뒤집으므로 특정 항목만 반대로 정렬하려는 조건과 구별해야 한다.
정렬하면 비교할 대상이 줄어든다
자재 길이 문제를 모든 쌍으로 풀면 첫 자재와 나머지, 둘째 자재와 그 뒤의 자재를 차례로 비교한다. 쌍의 수가 n(n - 1) / 2이므로 시간은 O(n²)이다. 이 방법은 짧고 직접적이어서 작은 입력의 정답을 만드는 데 적합하다.
길이를 정렬하면 이웃한 두 값의 차이만 확인해도 된다. 정렬 결과가 [7, 12, 18, 30]이면 차이는 5, 6, 12다. 이 중 가장 작은 5가 답이다.
왜 떨어진 두 값은 검사하지 않아도 되는가. 정렬된 값 a, b, c가 이 순서에 있다면 c - a는 b - a보다 작지 않다. 더 많은 값이 사이에 있어도 같은 설명이 성립한다. 따라서 떨어진 두 값이 만드는 차이보다 크지 않은 이웃 차이가 그 사이에 존재한다. 최소 차이는 이웃한 쌍 중에서도 얻을 수 있다.
이웃을 순회하는 동안에는 지금까지 확인한 모든 이웃 차이의 최솟값을 답으로 유지한다. 다음 차이와 현재 답 중 작은 것을 선택하면 이 사실이 계속 유지된다. 정렬에 O(n log n), 순회에 O(n)이 걸리므로 전체 시간은 O(n log n)이다. 새 정렬 목록을 만드는 아래 구현의 추가 공간은 O(n)이다.
접수 목록은 기준을 잘 정하는 문제이고, 자재 길이는 정렬 후 살펴볼 대상을 줄이는 문제다. 다른 활용으로는 같은 이름을 모아 묶거나, 시간순 기록에서 사건 사이의 간격을 구하는 일이 있다. 정렬을 적용할 때는 원래 위치가 필요한지 먼저 확인해야 한다. 필요하다면 위치도 기록에 함께 보관한다.
완성 코드
다음 프로그램을 main.py에 저장한다. 외부 입력을 기다리지 않으며 표준 라이브러리만 사용한다. 접수 목록은 문자열을 파일처럼 읽어 코딩 테스트의 입력 처리를 흉내 낸다. 선택·삽입·퀵 정렬은 정수 목록을 다루고, 병합 정렬은 키 함수를 받아 접수 기록도 처리한다.
import io
import random
from itertools import product
def selection_sort(values):
data = list(values)
for start in range(len(data) - 1):
smallest = start
for pos in range(start + 1, len(data)):
if data[pos] < data[smallest]:
smallest = pos
data[start], data[smallest] = data[smallest], data[start]
return data
def insertion_sort(values):
data = list(values)
for pos in range(1, len(data)):
value = data[pos]
left = pos - 1
while left >= 0 and data[left] > value:
data[left + 1] = data[left]
left -= 1
data[left + 1] = value
return data
def quick_sort(values):
data = list(values)
def arrange(lo, hi):
if lo >= hi:
return
pivot = data[hi]
boundary = lo
for scan in range(lo, hi):
if data[scan] <= pivot:
data[boundary], data[scan] = data[scan], data[boundary]
boundary += 1
data[boundary], data[hi] = data[hi], data[boundary]
arrange(lo, boundary - 1)
arrange(boundary + 1, hi)
arrange(0, len(data) - 1)
return data
def merge_sort(values, key=lambda value: value):
decorated = [(key(value), value) for value in values]
def divide(items):
if len(items) <= 1:
return items
middle = len(items) // 2
left = divide(items[:middle])
right = divide(items[middle:])
merged = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i][0] <= right[j][0]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
return [value for _, value in divide(decorated)]
def slow_stable_sort(values, key):
remaining = list(values)
result = []
while remaining:
best = 0
for pos in range(1, len(remaining)):
if key(remaining[pos]) < key(remaining[best]):
best = pos
result.append(remaining.pop(best))
return result
def record_key(row):
return row[1], row[2]
def minimum_gap(values):
if len(values) < 2:
return None
ordered = sorted(values)
best = ordered[1] - ordered[0]
for pos in range(2, len(ordered)):
best = min(best, ordered[pos] - ordered[pos - 1])
return best
def slow_minimum_gap(values):
best = None
for left in range(len(values)):
for right in range(left + 1, len(values)):
gap = abs(values[left] - values[right])
if best is None or gap < best:
best = gap
return best
def verify():
integer_cases = 0
gap_cases = 0
for size in range(6):
for values in product(range(3), repeat=size):
expected = slow_stable_sort(values, key=lambda value: value)
assert selection_sort(values) == expected
assert insertion_sort(values) == expected
assert quick_sort(values) == expected
assert merge_sort(values) == expected
assert minimum_gap(values) == slow_minimum_gap(values)
integer_cases += 1
if size >= 2:
gap_cases += 1
record_cases = 0
for size in range(5):
for grades in product(range(2), repeat=size):
rows = [(f"R{pos}", grade, 5)
for pos, grade in enumerate(grades)]
expected = slow_stable_sort(rows, key=record_key)
assert merge_sort(rows, key=record_key) == expected
record_cases += 1
rng = random.Random(606)
random_cases = 200
for _ in range(random_cases):
size = rng.randrange(41)
values = [rng.randrange(-20, 21) for _ in range(size)]
assert merge_sort(values) == sorted(values)
rows = [(f"R{pos}", rng.randrange(3), rng.randrange(4))
for pos in range(size)]
assert merge_sort(rows, key=record_key) == sorted(
rows, key=record_key
)
return integer_cases, gap_cases, record_cases, random_cases
def main():
source = io.StringIO("4\nB 2 5\nA 1 8\nC 2 3\nD 2 5\n")
count = int(source.readline())
records = []
for _ in range(count):
name, grade, minutes = source.readline().split()
records.append((name, int(grade), int(minutes)))
ordered = merge_sort(records, key=record_key)
assert ordered == sorted(records, key=record_key)
print("접수 순서:", " ".join(row[0] for row in ordered))
print("자재 최소 차이:", minimum_gap([18, 7, 12, 30]))
integers, gaps, records_checked, randoms = verify()
print(f"정수 전수 대조: {integers}개 통과")
print(f"두 개 이상인 자재 전수 대조: {gaps}개 통과")
print(f"접수 안정성 전수 대조: {records_checked}개 통과")
print(f"무작위 대조: {randoms}회 통과")
if __name__ == "__main__":
main()줄별 해설
import io는 문자열을 입력 파일처럼 읽는 데 사용한다. random은 재현 가능한 입력 생성에, product는 정해진 값으로 만들 수 있는 모든 짧은 목록을 생성하는 데 사용한다. 목록을 파일에서 읽거나 외부 패키지를 설치할 필요는 없다.
selection_sort의 data = list(values)는 입력의 복사본을 만든다. start는 이번에 확정할 자리이고, smallest는 검사한 구간에서 가장 작은 값의 위치다. 안쪽 반복이 끝난 뒤 교환하면 앞부분의 확정된 자리가 하나 늘어난다. 같은 값이면 smallest를 바꾸지 않지만, 멀리 떨어진 원소를 교환하므로 안정성이 보장되지는 않는다.
insertion_sort의 value는 이번에 삽입할 값이다. left는 그 값과 비교할 앞쪽 위치다. while 조건은 먼저 위치가 유효한지 검사하고, 그다음 값을 비교한다. 큰 값만 오른쪽으로 밀고 left를 줄인다. 반복이 끝난 뒤 left + 1이 삽입할 자리다. left가 -1까지 줄어들면 맨 앞에 넣는다.
quick_sort의 arrange는 양 끝을 포함하는 구간을 받는다. 빈 구간이나 원소 하나인 구간은 lo >= hi에서 끝난다. scan은 기준값이 놓인 마지막 자리를 제외하고 검사한다. boundary는 기준값 이하인 구역의 다음 빈자리다. 마지막 교환으로 기준값을 경계에 배치한 뒤, 그 자리를 제외한 양쪽 구간만 재귀 호출한다.
merge_sort의 decorated는 기준값과 원래 값을 묶는다. 키 함수는 이 줄에서 원소마다 한 번 호출된다. 이후 비교에서는 left[i][0]과 right[j][0]만 사용한다. 묶음 전체를 비교하면 기준값이 같은 경우 식별자 같은 원래 값까지 비교할 수 있으므로 의도적으로 기준값만 꺼낸다.
divide의 종료 조건은 길이가 1 이하인 경우다. 가운데를 기준으로 자른 두 목록을 먼저 정렬한다. i와 j는 각 결과에서 아직 꺼내지 않은 첫 위치다. 비교에서 <=를 사용해 동률이면 왼쪽을 먼저 넣는다. append 이후에는 꺼낸 쪽 위치만 증가한다. 반복이 끝나면 extend로 남은 원소를 붙인다. 맨 마지막 줄은 계산용 기준값을 제거하고 원래 값만 반환한다.
slow_stable_sort는 남은 원소를 매번 처음부터 검사하는 느린 정답이다. 더 작은 값이 나왔을 때만 best를 바꾸므로 같은 기준값에서는 먼저 남아 있던 기록을 고른다. pop은 그 기록을 꺼내면서 나머지 기록의 상대적인 순서를 유지한다. 비교와 이동을 합쳐 시간은 O(n²), 추가 공간은 O(n)이다.
minimum_gap은 두 개 미만이면 None을 반환한다. 첫 이웃 차이로 best를 초기화했으므로 특별히 큰 수를 준비할 필요가 없다. slow_minimum_gap은 left보다 뒤에 있는 모든 위치를 조사하고 절댓값으로 차이를 구한다. 정렬을 사용하지 않으므로 빠른 풀이와 다른 관점에서 답을 확인한다.
verify의 첫 두 반복은 길이 0부터 5까지, 각 원소가 0·1·2인 모든 목록을 만든다. 경우의 수는 1 + 3 + 9 + 27 + 81 + 243 = 364다. 네 정렬 결과를 느린 정답과 비교하고 자재 문제의 결과도 모든 쌍 검사와 비교한다. 빈 목록과 원소 하나인 목록의 None 반환도 이 과정에서 확인한다.
접수 안정성 검사는 길이 0부터 4까지 등급 0·1의 모든 배열을 만든다. 시간은 5로 고정하고 식별자는 입력 위치에 따라 붙여 같은 기준값을 가진 기록의 순서를 관찰한다. 경우의 수는 1 + 2 + 4 + 8 + 16 = 31이다. 기준값만 비교하면 안정성 오류를 놓칠 수 있으므로 식별자를 포함한 기록 전체를 비교한다.
random.Random(606)은 이 검사만의 난수 생성기를 만든다. 매회 정수 목록과 접수 기록을 각각 검사한다. 무작위 검사는 입력 범위를 넓혀 주지만 정확성의 증명을 대신하지는 않는다. 작은 입력 전수 대조도 설정한 범위 안의 누락과 구현 실수를 찾는 도구다.
main의 readline은 준비된 문자열에서 한 줄씩 읽는다. 숫자 두 항목을 int로 바꾸고, 정렬 결과에서 식별자만 모아 출력한다. 마지막 조건문은 이 파일을 직접 실행했을 때 main을 호출한다. 검증에는 assert를 사용하므로 여기서는 최적화 옵션 없이 실행한다.
실행 결과
다음 명령은 문법 검사를 거친 뒤 프로그램을 실행한다. 문법 검사가 성공하면 별도 문구는 출력되지 않는다.
python3 -m py_compile main.py
python3 main.py예상 출력은 다음과 같다. 무작위 입력의 시작값이 고정되어 있고 검사 개수만 출력하므로 실행할 때마다 같다. 무작위 대조 1회에는 정수 목록과 접수 목록 검사가 각각 들어 있다.
접수 순서: A C B D
자재 최소 차이: 5
정수 전수 대조: 364개 통과
두 개 이상인 자재 전수 대조: 360개 통과
접수 안정성 전수 대조: 31개 통과
무작위 대조: 200회 통과A는 등급이 가장 작아 먼저 나온다. 등급 2에서는 시간이 3인 C가 앞선다. B와 D는 등급과 시간이 모두 같으므로 원래 접수 순서대로 남는다. 자재 전수 대조의 360개는 길이가 2 이상인 경우만 센 값이며, 함수 결과 비교 자체는 더 짧은 경우에도 실행된다.
실무에서 자주 틀리는 것
sort의 반환값을 정렬 결과로 받는다
다음 코드는 ordered에 None을 저장한다. 정렬된 새 목록이 필요하면 sorted를 사용한다.
# 틀린 코드
ordered = records.sort(key=record_key)
# 고친 코드
ordered = sorted(records, key=record_key)원본 수정이 목적이면 records.sort(key=record_key)를 단독으로 호출하고 이후 records를 사용한다.
중요한 기준부터 여러 번 정렬한다
등급을 먼저 정렬하고 시간을 나중에 정렬하면 마지막 시간 정렬이 전체 순서를 결정한다. 등급이 우선이라는 조건을 지키려면 덜 중요한 기준부터 정렬하거나 튜플 기준을 사용한다.
# 틀린 코드
ordered = sorted(records, key=lambda row: row[1])
ordered.sort(key=lambda row: row[2])
# 고친 코드
ordered = sorted(records, key=lambda row: (row[1], row[2]))입력에서 숫자를 문자열로 둔 채 정렬하는 실수도 주의한다. "12"와 "3"은 문자열 비교에서 숫자 크기와 다른 순서를 만든다. 완성 코드처럼 입력을 읽을 때 정수로 바꾼다.
병합에서 동률일 때 오른쪽을 먼저 꺼낸다
동률일 때 오른쪽을 선택해도 숫자의 크기 순서는 맞는다. 그러나 원래 뒤에 있던 접수 기록이 앞으로 오므로 안정성이 깨진다.
# 틀린 코드: 같으면 else에서 오른쪽을 선택한다
if left[i][0] < right[j][0]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# 고친 코드: 같으면 왼쪽을 선택한다
if left[i][0] <= right[j][0]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1이 이유로 정수의 정렬 여부만 검사하지 않고 식별자가 다른 동률 기록도 검사해야 한다.
정렬하지 않은 목록에서 이웃만 비교한다
입력에서 가까운 위치와 값이 가까운 것은 다르다. [7, 30, 12]의 입력상 이웃 차이는 23과 18이지만 실제 최소 차이는 5다.
# 틀린 코드
best = min(abs(values[i] - values[i - 1])
for i in range(1, len(values)))
# 고친 코드
best = minimum_gap(values)고친 함수는 정렬한 뒤 이웃을 검사하며, 원소가 부족한 경우도 처리한다. 빈 후보에 min을 호출하면 예외가 발생하므로 비교할 쌍이 없는 입력의 의미를 먼저 정해야 한다.
한눈에 보기
| 방법 | 유지하는 사실 | 시간 | 안정성 |
|---|---|---|---|
| 선택 정렬 | 앞부분은 전체의 작은 값부터 확정된다 | O(n²) | 보장하지 않는다 |
| 삽입 정렬 | 처리한 앞부분이 정렬되어 있다 | 최선 O(n), 최악 O(n²) | 큰 값만 밀면 보장한다 |
| 병합 정렬 | 꺼낸 원소들이 올바른 결과의 앞부분이다 | O(n log n) | 동률에 왼쪽을 고르면 보장한다 |
| 퀵 정렬 | 기준값 이하와 초과인 구역을 구분한다 | 균형 시 O(n log n), 최악 O(n²) | 이 구현은 보장하지 않는다 |
위 시간은 비교와 키 계산을 상수 시간으로 볼 때의 설명이다. 완성 코드의 네 함수는 입력을 복사하므로 모두 최소 O(n)의 추가 공간을 사용한다. 병합 정렬은 별도 목록을 만들고, 퀵 정렬은 분할 상태에 따라 재귀 호출 공간이 달라진다.
실제 문제에서는 내장 정렬로 기준을 표현하는 것부터 검토한다. 직접 구현한 정렬은 불변식과 안정성을 이해하고 검증하는 데 사용한다. 정렬 후에는 이웃 비교, 같은 값 묶기, 순서에 따른 처리처럼 새로 가능해진 작업을 찾는다. 다음 장에서는 정렬된 순서로 후보 범위를 줄이는 방법을 살펴본다.
연습 문제
- 접수 기록을 등급 오름차순, 예상 작업 시간 내림차순으로 정렬하라. 두 값이 같으면 접수 순서를 유지한다. 완성 코드의 예시 기록에서 식별자 출력 순서를 구하고, 튜플 기준과 두 번 정렬하는 방법을 각각 작성하라.
- 이름만 다른 기록 [("가", 2), ("나", 2), ("다", 1)]이 있다. 두 번째 항목을 기준으로 선택 정렬의 첫 교환을 수행하라. 결과를 쓰고, 삽입 정렬이 안정성을 지키려면 이동 조건에 어떤 비교를 써야 하는지 설명하라.
- 자재 길이가 [14, 8, 14, 25]일 때 최소 차이를 구하라. 길이가 같은 두 자재를 하나로 합쳐도 되는지 설명하고, 길이가 두 개 미만일 때의 반환값도 쓰라.
- 접수 안정성 전수 검사에서 등급뿐 아니라 시간도 0 또는 1로 바꾸고 싶다. 길이 0부터 3까지 모든 입력을 만들 때 검사할 경우의 수를 구하고, 입력 생성 코드를 작성하라.
정답과 해설
-
출력 순서는 A B D C다. A는 등급 1이므로 먼저 오고, 등급 2에서는 시간이 5인 B와 D가 시간 3인 C보다 먼저 온다. B와 D의 동률은 원래 순서를 유지한다.
ordered = sorted(records, key=lambda row: (row[1], -row[2])) ordered_twice = sorted(records, key=lambda row: row[2], reverse=True) ordered_twice.sort(key=lambda row: row[1]) assert ordered == ordered_twice두 번 정렬할 때는 덜 중요한 시간 기준을 먼저 적용한다. 이후 안정적인 등급 정렬이 같은 등급 내부의 시간 순서를 유지한다. 키 계산이 상수 시간이면 두 방식 모두 시간 O(n log n), 추가 공간 O(n)이다.
-
최솟값인 ("다", 1)을 첫 원소와 교환하면 [("다", 1), ("나", 2), ("가", 2)]가 된다. 같은 기준값 2를 가진 가와 나의 순서가 뒤집힌다. 삽입 정렬에서는 앞 원소의 기준값이 새 기준값보다 클 때만 이동해야 한다. >=를 쓰면 같은 기준값도 밀어 새 기록이 먼저 오게 된다.
-
정렬 결과는 [8, 14, 14, 25]이고 이웃 차이는 6, 0, 11이므로 답은 0이다. 같은 길이의 자재도 서로 다른 물건이므로 하나로 합치면 안 된다. 중복을 제거하면 정답 0을 잃을 수 있다. 길이가 두 개 미만이면 완성 코드의 약속에 따라 None을 반환한다.
-
기록 하나의 등급·시간 조합은 네 가지다. 길이별 경우의 수를 더하면 1 + 4 + 16 + 64 = 85다. 입력 위치로 식별자를 붙이면 같은 기준값을 가진 기록의 원래 순서를 검사할 수 있다.
options = list(product(range(2), repeat=2)) checked = 0 for size in range(4): for attributes in product(options, repeat=size): rows = [(f"R{pos}", grade, minutes) for pos, (grade, minutes) in enumerate(attributes)] expected = slow_stable_sort(rows, key=record_key) assert merge_sort(rows, key=record_key) == expected checked += 1 assert checked == 85길이 상한을 늘리면 경우의 수가 빠르게 커진다. 전수 검사는 작은 범위에서 촘촘히 수행하고, 더 긴 입력은 고정된 난수와 경계 사례로 보완한다. 정확성의 근거는 각 정렬이 유지하는 불변식과 재귀의 귀납에 둔다.