[Sort] 삽입정렬 - Insertion Sort

앞에 있는 array들이 정렬되어있고 현재 위치의 값을 앞 정렬된 array 중, 알맞은 곳에 삽입하는 방법

-> 코드화 하면 삽입보다는 뒤에서 앞으로 하나씩 검사(현재 위치의 값과 비교)해서 SWAP해나가는 방식

머릿속에서는 삽입이지만 사실 뒤에서부터 앞방향으로 검사 & SWAP 해서 자리 찾아가는 방식

 

시간복잡도

For문이 2번 중첩되어 최악의 경우 뒤에서 앞으로 모든 검사를 다하며 찾아가서 선택정렬과 O(n^2)으로 비슷하겠지만

데이터가 정렬이 거의 되어 있는 상태라면 각 idx에 대해서 검사시간이 줄어들어 빠르게 동작한다

 

import sys
input = sys.stdin.readline

arr = [4, 2, 6, 1, 9, 23, 45, 21, 28, 19]

def insertionSort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j-1] > arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
            else:
                break
        

insertionSort(arr)
print(arr)