정렬의 계약·안정성·측정 비교
정답 검사와 시간 측정을 구분하고 후속 정렬의 선택 기준을 만듭니다.
서로 다른 정렬을 같은 조건으로 비교하려면 무엇을 확인해야 할까요? 목표는 오름차순 여부만 보지 않고 원소 보존·원본 보존·안정성·작업 비용까지 점검하는 것입니다. 세 기본 정렬과 복잡도를 먼저 읽으세요.
개념과 약속
정렬 결과는 순서가 맞아야 하고 입력과 같은 원소를 같은 개수만큼 가져야 합니다. [1,1,2]에서 [1,2]를 만들면 오름차순이어도 정답이 아닙니다. sorted(values)는 독립적인 참조 결과로 사용합니다. Python의 정렬은 안정 정렬이며 key로 정렬 기준을 선택할 수 있습니다. 공식 Sorting HOWTO에서 동률과 여러 키 정렬을 확인할 수 있습니다.
실행 시간을 한 번 측정한 결과는 증가율의 증명이 아닙니다. 난수 입력의 시드·크기·자료 분포를 같게 하고 여러 번 측정해야 합니다. 이 본문은 흔들리는 시간을 고정된 정답으로 쓰지 않고, 재현 가능한 결과 검사부터 합니다. 제자리라는 말은 보조 공간을 거의 쓰지 않는 작업 방식이지 원본을 반드시 보존한다는 뜻이 아닙니다.
손으로 상태 추적하기
| 방법 | 최선 | 최악 | 동률 안정성 | 이 구현의 원본 |
|---|---|---|---|---|
| 버블(조기 종료) | Θ(n) | Θ(n²) | 보존 | 보존 |
| 선택 | Θ(n²) | Θ(n²) | 일반적으로 미보존 | 보존 |
| 삽입 | Θ(n) | Θ(n²) | 보존 | 보존 |
원본을 보존하는 복사 비용 O(n)을 세 방법 모두 똑같이 포함합니다.
직접 실행하기
아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.
def bubble_sort(values):
result = list(values)
for end in range(len(result) - 1, 0, -1):
changed = False
for i in range(end):
if result[i] > 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):
result = list(values)
for i in range(len(result) - 1):
smallest = i
for j in range(i + 1, len(result)):
if result[j] < result[smallest]:
smallest = j
result[i], result[smallest] = result[smallest], result[i]
return result
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
cases = [[], [1], [3, 1, 3, 2], [4, 3, 2, 1], [1, 2, 3, 4]]
for sort_function in [bubble_sort, selection_sort, insertion_sort]:
for values in cases:
before = list(values)
assert sort_function(values) == sorted(values)
assert values == before
print(sort_function.__name__, "통과")
records = [(2, "A"), (1, "X"), (2, "B")]
print(sorted(records, key=lambda item: item[0]))실행 결과:
bubble_sort 통과
selection_sort 통과
insertion_sort 통과
[(1, 'X'), (2, 'A'), (2, 'B')]왜 맞고 언제 끝나는가
참조 결과와 목록 전체를 비교하면 순서와 중복 개수를 함께 검사합니다. 별도로 원본이 바뀌지 않았는지 확인합니다. 다만 이 다섯 입력의 성공은 일반 증명을 대신하지 않습니다. 앞 본문의 불변조건 설명과 함께 사용해야 합니다.
비용과 적용 범위
세 방법은 작은 입력에서 읽기 쉽지만 큰 임의 자료에는 이차 비용이 커집니다. 후속 병합 정렬은 최악 O(n log n), 힙 정렬도 최악 O(n log n)을 제공합니다. 실제 제품 코드에서는 검증된 언어의 정렬을 우선하고, 직접 구현은 원리·제약·특수 문제를 이해하기 위해 사용합니다.
스스로 풀어 보기
- 빈 입력·중복 입력·정렬된 입력은 각각 어떤 실패를 찾기 좋은가요?
- 시간 측정 입력을 10배로 늘렸을 때 선형과 이차 연산 횟수는 대략 몇 배인가요?
힌트
- 반복 경계·원소 보존·조기 종료를 생각하세요.
- n과 n²에 10n을 대입합니다.
해설
- 빈 입력은 잘못된 첫 원소 접근, 중복은 값 누락과 동률 처리, 정렬된 입력은 종료·이동 불필요 동작을 점검합니다.
- 각각 약 10배와 100배입니다. 실제 시간은 고정 비용과 환경 때문에 정확히 이 비율이 되지 않을 수 있습니다.
흔한 오해
정렬된 결과의 동률 숫자만으로 안정성을 증명하지 못합니다. 동률 항목에 A·B처럼 신원을 붙이고 키만 비교해야 합니다.
복습과 다음 연결
다음 재귀에서 큰 문제를 작은 문제로 나누기 위한 호출 구조를 익힙니다.