Insertion Sort

Insertion Sort는 이름에서 드러나듯 값을 어딘가(?)에 넣어서 정렬한다.

글로는 어려 울 수 있으니 간단히 Flow를 확인하면 다음과 같다.

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.

5, 6, 11, 12, 13

위의 Flow에서 확인 할 수 있듯이 공통적인 부분은 인덱스에 있는 값을 이미 정렬되어 있는 배열에 순서에 맞추어 넣는 것이다.

(도입 부분에 말한 어딘가는 정렬되어 있는 배열이다.)

그럼 코드로 확인해보도록 하자.

def insertionSort(arr):
    # Traverse through 1 to len(arr) 
    for i in range(1, len(arr)):

        key = arr[i]

        # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

Insertion Sort는 전체적으로 메인 배열을 2개의 서브 배열로 나누어 사용한다. (서브 배열은 각각 정렬된 배열과 정렬되지 않은 배열이다.)

그래서 중첩된 for-loop 중 첫 번째 for-loop은 졍렬되지 않은 배열에서 차례대로 인덱스를 선택하는 것이고, 두 번째 for-loop은 정렬된 배열에서 선택된 인덱스 값을 넣을 만한 곳을 찾는 것이다. (내장된 for-loop을 면밀히 살펴보면 정렬된 배열의 가장 마지막부터 하나씩 찾고 있다.)

그림 1. Insertion Sort

이제 까지 알아본 것을 바탕으로 그림 1을 살펴보면 Insertion Sort가 어떻게 정렬이 되는지 확인 할 수 있다.

Insertion의 시간 복잡도는 당연스럽게도 O(n^2)이다. 그런데 한 가지 정렬된 배열에 값을 넣어야 할 위치를 바로 찾는다면 사실상 O(n)에 가까울 수 있다. (물론 이것은 Best Case 일 때) 공간 복잡도는 O(1)로 정렬자체가 메인 배열 내부에서 동작하기 때문에 메모리 추가 없이 수행 할 수 있다.

Reference

- https://www.geeksforgeeks.org/insertion-sort/