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

손에 든 카드가 이미 정렬되어 있다면 새 카드 하나를 어디에 넣을지 찾으면 됩니다. 목표는 '앞부분이 정렬되어 있다'는 불변조건과 값을 덮어쓰기 전에 저장하는 이유를 이해하는 것입니다. 리스트 인덱스와 이전 정렬 본문을 복습하세요.

개념과 약속

인덱스 i 전까지의 앞부분을 정렬된 구간으로 둡니다. current에 새 값을 따로 저장하고, 왼쪽의 값이 더 크면 오른쪽으로 한 칸씩 밉니다. 현재 값보다 크지 않은 값 또는 목록 경계를 만나면 빈 자리에 current를 넣습니다. j >= 0 and ...에서 왼쪽 조건을 먼저 확인하므로 범위를 벗어난 검사 전에 멈춥니다. Python의 음수 인덱스는 뒤에서 세므로 경계 검사를 생략하면 오류 없이 잘못된 값이 읽힐 수도 있습니다.

같은 키는 밀지 않는 > 조건으로 안정성을 지킵니다. 비교 대상으로 빼 둔 현재 값은 하나이고, 밀기는 교환과 다릅니다. 매번 이웃 두 값을 바꿀 필요가 없습니다.

손으로 상태 추적하기

입력 [4,2,3,1]의 i=2 단계입니다.

중간에 목록 안의 3이 덮여도 current에 보존되어 원소를 잃지 않습니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

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인 앞부분이 정렬되어 있습니다. 더 큰 값들을 오른쪽으로 밀어 순서를 보존하고 올바른 틈에 current를 넣으면 길이 i+1인 앞부분도 정렬됩니다. 마지막에 앞부분이 전체가 됩니다. 안쪽 반복의 j는 줄고 바깥 i는 유한한 범위를 지나므로 끝납니다.

비용과 적용 범위

역순 입력에서는 각 원소가 앞의 모든 값을 밀어 Θ(n²)입니다. 정렬된 입력에서는 각 차례의 비교가 바로 끝나 Θ(n)입니다. 거의 정렬된 작은 자료에 유용합니다. 내부 보조 공간 O(1)에 원본 보존용 복사 O(n)이 추가됩니다.

스스로 풀어 보기

1. [3,1,2]의 각 i 단계 뒤 목록을 쓰세요.
2. current 저장 없이 목록 값만 계속 오른쪽으로 밀면 어떤 원소를 잃나요?

힌트

1. 먼저 1을 3 앞에 넣습니다.
2. 비교할 새 값의 원래 칸도 덮입니다.

해설

1. i=1 뒤 [1,3,2], i=2 뒤 [1,2,3]입니다.
2. 현재 삽입하려던 값을 잃어 같은 값이 중복될 수 있습니다. 임시 변수는 단순한 장식이 아니라 보존을 위한 상태입니다.

흔한 오해

삽입 정렬이 항상 버블보다 빠르다는 보장은 없습니다. 입력 분포·구현·상수 비용에 따라 달라지며 최악 증가율은 같은 이차 규모입니다.

복습과 다음 연결

정렬 비교를 통해 계약과 측정을 확인한 뒤 재귀로 넘어갑니다.