[알고리즘] 3) 삽입 정렬 알고리즘

삽입 정렬 알고리즘

삽입 정렬은 리스트의 범위를

2 -> 3 -> 4개 씩 늘려나가면서 새롭게 추가된 인자를 기존 값들과 비교하는 알고리즘. 

설명

1. 아래 인자들이 [2,1] 부터 차례대로 5, 4, 3 입력 받는다고 가정한다. 

[2, 1, 5, 4, 3]

2. 처음에 두 인자를 비교한 후에 정렬을 수행한다. 

[2, 1]: 2 > 1 => swap
 ^  ^
[1, 2]
 *  *

3. 그 다음 기존의 정렬 범위에 한칸을 확장하여 세번째 값을 추가시키고 비교 진행한다. 

5와 2를 비교하여 움직임이 없었다는 것은 1과의 비교도 진행할 필요가 없다는 것을 의미하므로 종료하고 다음 인자를 입력 받는다. 

[1, 2, 5]: 2 < 5 => OK
    ^  ^
[1, 2, 5]
 *  *  *

4. 4를 입력받은 후에 스와핑을 진행. 마찬가지로 스와핑을 더이상 진행하지 않아도 된다면 넘어간다. 

[1, 2, 5, 4]: 5 > 4 => swap
       ^  ^
[1, 2, 4, 5]: 2 < 4 => OK
    ^  ^
[1, 2, 4, 5]
 *  *  *  *

위의 방법으로 작동되는 방식을 삽입 정렬 알고리즘이라고 한다. 

파이썬 구현

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

[최적화] 

기존에 있던 값들은 이전 절차에서 모두 정렬되었다는 점을 감안하여 새롭게 '추가'된 값보다 작은 숫자를 만나는 최초의 순간까지만 반복문을 수행. 

def insertion_sort(arr):
    for end in range(1, len(arr)):
        to_insert = arr[end]
        i = end
        while i > 0 and arr[i - 1] > to_insert:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = to_insert

해당 최적화를 적용하면 O(N)의 시간 복잡도를 달성할 수 있음.