[Algorithm] Insertion Sort(삽입 정렬)

Insertion Sort

삽입 정렬은 2번째 원소부터 시작하여, 현재 index를 기준으로 자신보다 앞에 있는 원소들에 대해 적절한 위치를 찾아 삽입하는 정렬 방식이다.
Selection Sort 와 유사하지만 거의 정렬이 되어있는 배열에서는 더 유리한 알고리즘이다.
ex)[1,2,4,5,6]의 배열에 3이라는 숫자 삽입

안정 정렬(stable sort) 에 속한다.

구현 방법

현재 index의 값을 임시저장하고, 해당 index기준 앞쪽의 배열은 이미 정렬이 되어있다고 가정하며 진행한다. 현재 index를 하나씩 줄여가며 들어갈 수 있는 위치를 찾는다.

구현(Python)

import time

def insertion_sort(test):
    for i in range(1, len(test)):
        temp = test[i]
        idx = i-1
        while idx >= 0 and test[idx] > temp:
            test[idx+1] = test[idx]
            idx -= 1
        test[idx+1] = temp
    print(test)


if __name__ == '__main__':
    start = time.time()  # 시작 시간 저장
    test = [4,6,2,8,9,7,1]
    insertion_sort(test)
    print("time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

결과

[1, 2, 4, 6, 7, 8, 9]
time : 3.0994415283203125e-05

시간복잡도

배열이 역으로 되어있는 최악의 경우에는 (n-1)+(n-2)+...+1 = O(n^2) 이 나온다.
하지만 거의 정렬이 되어있는 경우에는 한 사이클 당 한 번의 비교, swap 만 필요하기 때문에 최선의 경우 O(n)이 된다.

공간복잡도

배열 내부에서 교환하면서(swap)진행하는 알고리즘, 즉 in-place sorting 이므로 O(n)의 복잡도를 가진다.