삽입 정렬(Insertion Sort)의 개념

삽입 정렬은 주어진 데이터를 하나씩 뽑아서, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은 데이터를 바른 위치에 삽입해 정렬하는 방식입니다. 아래의 흐름을 가집니다.

1. 첫 번째 요소를 정렬된 부분으로 간주합니다. 정렬된 부분은 초기에 하나의 요소만 포함합니다.
2. 다음 요소를 선택하고, 이미 정렬된 배열 부분에서 이 요소가 들어갈 올바른 위치를 찾습니다.
3. 선택된 요소를 그 위치에 삽입하고, 필요하다면 원래 있던 요소들을 오른쪽으로 이동시켜 공간을 만듭니다.
4. 배열의 모든 요소가 정렬될 때까지 이 과정을 반복합니다.

삽입 정렬의 Python 구현

Python 으로 삽입 정렬을 아래와 같이 구현할 수 있습니다.

def insertion_sort(arr: list) -> None:
    # 배열의 두 번째 요소부터 시작
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # key보다 앞에 있는 요소들을 순회하면서, key가 이 요소보다 작으면 요소를 오른쪽으로 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # key를 빈 자리에 삽입
        arr[j + 1] = key

위의 알고리즘은 아래와 같은 흐름으로 동작합니다.

배열의 두 번째 요소 3을 key 로 하는 첫 번째 루프가 시작됩니다. 해당 값이 key 가 됩니다. key 를 기준으로 앞의 수인 1과 비교하고, 1이 3보다 작으므로 요소를 옮기지 않습니다. 이후 arr[j + 1] = key 가 수행됩니다.

    ^
[1, 3, 2, 5, 4]

이제 배열의 세 번째 요소 2가 key 가 됩니다. 2를 기준으로 왼쪽으로 비교해나가며 만약 왼쪽 수인 3보다 작다면 3을 오른쪽으로 이동시킵니다.

       ^                    # 3을 오른쪽으로 이동시킴
[1, 3, 2, 5, 4] -> 3>2 -> [1, ??, 3, 2, 5, 4]

이후 2와 1을 비교하지만, 1은 2보다 작으므로 1을 오른쪽으로 이동시키지 않습니다. 결국 2는 두 번째 자리에 삽입됩니다.

# 1, 2 비교 -> pass, ?? 위치에 2가 삽입됨
[1, 2(??), 3, 5, 4]

이제 5가 key 가 됩니다. 3과 비교하고 3은 5보다 작으므로 오른쪽으로 이동시키지 않습니다. 삽입 위치도 현재 인덱스 그대로에 삽입됩니다.

          ^
[1, 2, 3, 5, 4]

이제 4가 key 가 됩니다. 앞의 수 5와 비교했는데, 5가 더 크므로 5를 오른쪽으로 이동합니다.

             ^
[1, 2, 3, 5, 4] -> 5>4 -> [1, 2, 3, ??, 5, 4]

이제 3과 4를 비교하지만, 4는 3보다 작지 않습니다. 3을 오른쪽으로 이동시키지 않고, 4는 3 다음에 삽입됩니다.

[1, 2, 3, 4(??), 5]

삽입 정렬의 성능 분석과 특징

• 삽입 정렬 또한 이중 루프로 이루어집니다. 바깥 루프가 수행되는 동안, 안쪽 루프에서 그 앞의 데이터들과의 비교를 수행하죠. 1, 2, ... n-1 까지 비교를 수행하므로 시간 복잡도는 O(n) 이 됩니다.
• 입력이 거의 정렬된 경우, while 루프가 돌 필요가 거의 없으므로 시간 복잡도는 O(n) 이 됩니다.
• 안정적인 정렬 알고리즘입니다.
• 추가적인 저장공간은 상수 개를 가지는 제자리 정렬입니다.