삽입 정렬은 2번째 원소부터 시작하여, 현재 index를 기준으로 자신보다 앞에 있는 원소들에 대해 적절한 위치를 찾아 삽입하는 정렬 방식이다.
Selection Sort 와 유사하지만 거의 정렬이 되어있는 배열에서는 더 유리한 알고리즘이다.
ex)[1,2,4,5,6]의 배열에 3이라는 숫자 삽입
안정 정렬(stable sort) 에 속한다.
현재 index의 값을 임시저장하고, 해당 index기준 앞쪽의 배열은 이미 정렬이 되어있다고 가정하며 진행한다. 현재 index를 하나씩 줄여가며 들어갈 수 있는 위치를 찾는다.
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)의 복잡도를 가진다.