def insertion(a):
for cur in range(1, len(a)): # 인덱스 0까지는 정렬이 되어있다고 치고 1부터 수행
temp = a[cur] # 자리를 찾아가려는 원소를 temp에 저장
prev = cur - 1 # a[cur-1]이 먼저 비교대상이 될 것임
while 0 <= prev and a[prev] > temp: # 대소 관계가 맞을 때까지 위치 교환
a[prev+1] = a[prev] # 한 칸 뒤로 땡겨
prev -= 1 # 교환해야 될 애를 더 찾아 나가기 위해 인덱스 1 줄이기
a[prev+1] = temp # 마지막으로 비교연산 한 곳+1의 위치에 삽입
arr = [3, 1, 4, 3, 9, 10, 0]
insertion(arr)
print(arr)
# Insertion Sort
# 두번째 원소부터 시작해서/앞에 위치한 애들과 비교를 해서/더 큰 애들을 뒤로 땡긴 후/순서가 맞는 곳에 삽입
# 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더해서 i+1개의 배열을 만드는 과정을 반복한다.
# bubble sort나 selection sort와는 달리 한 개짜리 배열에서 시작해서 그 크기를 하나씩 늘려 나가는 정렬이다.
# 시간복잡도: O(n^2)
# 공간복잡도: n
# 장점: 최선의 경우 O(n)으로 빠르다. 거의 다 정렬이 되어있는 경우 bubble이나 selection sort보다 효율적이다.
# 추가적인 메모리를 필요로 하지 않는다(in-place). 중복된 원소가 있는 경우 원래 순서를 보장한다(stable)
# 단점: 최악의 경우 O(n^2)로 그닥 효율적이지 않다.