[알고리즘] Insertion sort 란?

1. Insertion sort 코드

 

def insertion_sort2(arr):
    for n in range(1, len(arr)):
        j = n
        key = arr[j]
        i = j - 1
        while i >= 0 and arr[i] > key:
            arr[i + 1] = arr[i]
            i = i - 1
        arr[i + 1] = key


arr = [9, 8, 1, 7, 5, 3, 2, 6, 4]
insertion_sort(arr)
print(arr)

 

위의 코드는 Insertion Sort의 파이썬 코드다.

 

 

2. 기본 알고리즘

 

Insertion sort의 기본 원리는 카드를 들고있을때 정렬하는 것과 유사하다.

 

 

위의 사진처럼 카드를 양손에 쥐고있다고 하자.

왼손에는 무조건 정렬된 상태의 카드들을, 오른손에는 무작위로 선택된 카드들을 쥐고있다고 생각하자.

 

이제 오른손에 쥐고있던 카드 하나를 뽑아 왼손으로 넘기며 적절한 위치를 찾아가면 된다.

 

예를 들어 왼손에 [1, 2, 4] 이렇게 정렬된 카드들을 가지고 있고, 오른손에 있는 여러장의 카드 중 [3] 에 해당하는 카드를 선택했을 경우, 왼손으로 옮기며 적절한 위치인 '2와 4 사이'로 옮긴다.

 

 

그러면 결과적으로 왼손에 [1, 2, 3, 4] 이렇게 정렬된 카드를 가지게 된다.

 

이것이 Insertion Sort의 핵심 아이디어다. 이렇게 오른손에 있는 카드가 모두 왼손으로 갈때까지 계속해서 반복하면, 모든 카드들이 정렬될 것이다.

 

 

다시 코드를 살펴보자.

 

def insertion_sort2(arr):
    for n in range(1, len(arr)):
        j = n
        key = arr[j]
        i = j - 1
        while i >= 0 and arr[i] > key:
            arr[i + 1] = arr[i]
            i = i - 1
        arr[i + 1] = key


arr = [9, 8, 1, 7, 5, 3, 2, 6, 4]
insertion_sort(arr)
print(arr)

 

위의 예시에서 오른손에 있는 카드 중 하나를 선택하는 과정이 4번째 줄의 'key = arr[j]'이고, 선택한 카드를 왼손에 있는 정렬된 카드더미의 올바른 자리에 삽입하는 과정이 6 ~ 9 번째 줄이다.

 

이렇게 전체 배열이 모두 정렬될때까지 수행하면 정렬이 완료된다.

 

아래의 예시에서 노란색으로 선택된 숫자가 key 값이며, 해당 key 값은 왼쪽의 배열 중 적절한 위치로 가게 된다. 또한 이미 정렬된 상태의 배열은 연두색으로 표현하였다.

 

Insertion sort example

 

 

 

3. 시간복잡도

 

Insertion sort의 시간 복잡도의 경우, 총 2개의 루프가 존재하므로 n^2 이다.

 

best case의 경우, 미리 정렬된 상태이며 오직 n번의 비교과정만을 수행하면 되므로 시간복잡도가 n이다.

 

worst case의 경우, 역순으로 정렬된 상태이며 모든 경우에서 n번의 비교와 n번의 이동이 발생하므로 시간복잡도가 n^2이다.

 

 

위의 내용은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.