삽입 정렬(insertion sort) 알고리즘 이란?

삽입 정렬은 각 반복에서 정렬되지 않은 요소를 적절한 위치에 배치하는 정렬 알고리즘 이다.

삽입 정렬 순서

Ex) 9, 5, 1, 4, 3

다음의 배열이 있다고 한다.

1. 배열의 첫 번째 요소는 정렬된 것으로 간주한다. 두 번째 요소를 가져와서 별도로 KEY(5)로 빼낸다. 그리고 첫 번째 요소와 비교를 한다. 이때 KEY(5)값이 첫 번째 요소(9)보다 작으므로 첫 번째 요소 앞으로 삽입을 한다.

5, 9, 1, 4, 3

2. 이렇게 되었을때 두번째 까지 정렬이 끝나고 세 번째 요소를 다시 KEY(1)로 빼낸다. 그리고 그 앞 요소들과 하나씩 비교를 해 나가면서 KEY(1)값보다 더 작은 요소 뒤에 또는 자신보다 더 큰 요소 앞으로 삽입을 하는식으로 반복하면 된다.

1, 5, 9, 4, 3

3. KEY(1)은 자신보다 더 작은 요소가 없기 때문에 자신보다 큰 요소 앞으로 삽입한다. 이처럼 모든 인덱스를 돌면서 비교후 삽입을 하면 된다.

시간 복잡도

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # key보다 큰 원소들을 오른쪽으로 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        # key를 정렬된 부분에 삽입
        arr[j + 1] = key

# 사용 예시
my_list = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(my_list)

print("정렬된 리스트:", my_list)

위처럼 삽입정렬은 키값을 꺼내두고 자신보다 앞에있는 숫자들을 비교하면서 중간 중간에 삽입을 할수가 있다. 이때 시간 복잡도는 평균적으로 O(n^2)이지만, 최선의 경우(이미 정렬되어 있을 경우) O(n)이 될수 있다. 예를들어 정렬이 되어있다면 while이 한번씩만 일어나기 때문에 이중 반복문이 한번에 끝나는것으로 진행되기 때문이다.