삽입 정렬 알고리즘

삽입 정렬 알고리즘(insertion sort algorithm)

삽입 정렬(insertion sort)은 리스트를 반복하면서 각 항목을 이미 정렬된 부분 리스트의 올바른 위치에 "삽입"함으로써 동작합니다.

1. 리스트의 두 번째 항목에서 시작하여 왼쪽의 항목과 비교합니다.
2. 현재 항목이 왼쪽 항목보다 작으면 왼쪽 항목을 오른쪽으로 이동시킵니다.
3. 이를 현재 항목이 왼쪽 항목보다 크거나 왼쪽에 더 이상 항목이 없을 때까지 반복합니다.
4. 그런 다음 현재 항목을 마지막으로 비어 있는 위치에 삽입합니다.
5. 이 과정을 리스트의 모든 항목에 대해 반복합니다.

이를 파이썬 코드로 구현하면 다음과 같습니다:

def insertion_sort(arr: list[int]) -> list[int]:
    # 배열 전체를 반복하면서
    for i in range(1, len(arr)):
        key: int = arr[i]

        # 이미 정렬된 배열 부분에서 올바른 위치를 찾아가는 과정
        j: int = i - 1
        while j >=0 and key < arr[j] :
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

    return arr


if __name__ == "__main__":
    arr: list[int] = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    print(insertion_sort(arr))
    # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

예를 들어, 이 함수에 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] 배열을 전달하면,
3 과 1을 비교하고, 1 이 더 작으므로 순서를 바꿉니다. [1, 3, 4, 1, 5, 9, 2, 6, 5, 3, 5] 이렇게 바뀐 이후 3번째 인덱스인 4 를 비교하기 시작합니다. 4는 1 보다 크므로 지나가고, 3 보다 크므로 지나갑니다. 이런 식으로 배열의 마지막 인덱스까지 정렬을 진행합니다.

삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)입니다. 그러나 리스트가 이미 거의 정렬되어 있는 경우 삽입 정렬은 매우 효율적일 수 있으며, 이 경우 시간 복잡도는 O(n)이 됩니다.