삽입 정렬 알고리즘 원리, 코드, 시간 복잡도

쉬운 말로 설명하는 원리

첫 번째 요소를 길이 1인 정렬된 리스트로 봅니다. 두 번째 요소를 가져와 첫 번째 요소의 앞이나 뒤에 넣습니다. 세 번째 요소를 가져와 앞의 두 요소 사이 알맞은 위치에 넣습니다. 모든 요소를 넣을 때까지 계속합니다.

삽입하려면 새 요소를 따로 들고 있다가(이를 key라고 합니다) 정렬된 부분을 왼쪽으로 훑습니다. key보다 큰 요소는 모두 한 칸 오른쪽으로 옮깁니다. 크지 않은 요소를 만나거나 리스트의 시작에 닿으면 빈 자리에 key를 놓습니다.

단계별 예제

[12, 11, 13, 5, 6]을 정렬해 봅시다. 막대 앞 부분은 정렬된 부분입니다(아직 최종 위치는 아닙니다).

2단계를 보세요. 이미 제자리에 있는 요소는 비교 한 번이면 됩니다. 그래서 삽입 정렬은 거의 정렬된 입력에서 빠릅니다.

파이썬 구현

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

교환하는 대신 이동하면 옮긴 요소마다 한 번만 쓰므로, 교환 기반 버전보다 작업이 절반 정도입니다. 아래처럼 이진 탐색으로 삽입 위치를 찾을 수도 있습니다. 그러면 비교는 전체 O(n log n)으로 줄지만 이동은 여전히 O(n²)이므로 전체 시간은 O(n²) 그대로입니다.

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

시간 복잡도와 공간 복잡도

더 정확히는 실행 시간이 O(n + I)입니다. I는 역전(순서가 틀린 쌍)의 수입니다. 모든 요소가 최종 위치에서 최대 k칸 떨어져 있다면 I는 최대 n · k이므로 삽입 정렬은 O(n · k)이고, k가 작을 때 매우 빠릅니다.

삽입 정렬과 다른 정렬 비교

삽입 정렬은 요소가 엄밀히 더 큰 요소만 넘어 왼쪽으로 이동하므로 안정 정렬입니다. 또한 온라인 알고리즘이라서, 데이터가 도착하는 대로 정렬할 수 있고 언제든 정렬된 접두부를 유지합니다. 짧은 리스트에서는 오버헤드가 낮아 O(n log n) 알고리즘보다 빠릅니다. 그래서 Timsort(파이썬과 Java의 객체 정렬에 사용됨)는 짧은 런(run)을 이진 삽입 정렬로 정렬하고, 많은 퀵 정렬 구현도 작은 크기에서는 삽입 정렬로 전환합니다.

변형과 흔한 실수

• 이진 삽입 정렬: 위치를 이진 탐색으로 찾은 다음 이동합니다. 비교가 적어서 비교 비용이 클 때 도움이 됩니다.
• 셸 정렬: 일정 간격만큼 떨어진 요소끼리 삽입 정렬을 한 다음 간격을 1까지 줄입니다. 멀리 있는 요소를 빠르게 옮기므로 큰 배열에서는 일반 삽입 정렬보다 훨씬 빠릅니다.
• 연결 리스트 삽입 정렬: 요소를 이동할 필요는 없지만, 위치를 찾는 일은 여전히 선형 탐색입니다.

삽입 정렬을 쓰는 경우

작은 배열(수십 개 요소), 정렬한 뒤 몇 개만 추가한 리스트처럼 거의 정렬된 데이터, 단순한 안정 제자리 정렬이 필요할 때 쓰세요. 큰 무작위 데이터에는 O(n log n) 정렬을 쓰세요. 파이썬에서는 sorted()나 list.sort()이며, 이들은 내부적으로 작은 런에 이미 삽입 정렬을 적용합니다.

면접에서는 추적 과정, 최선과 최악의 경우, 안정 정렬인 이유, 작거나 거의 정렬된 입력에서 O(n log n) 알고리즘보다 빠른 이유를 묻는 경우가 많습니다.