# selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘
# insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후,
# 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬한다.
# 최선의 경우 O(N)이라는 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋음.
# Process
# 1. 정렬은 2번째 index의 값을 temp에 저장
# 2. temp와 이전에 있는 원소들과 비교하며 삽입한다.
# 3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.
def insertionSort(arr):
for i in range(1, len(arr)): # 두 번째 위치부터 시작,
temp = arr[i] # 해당 값을 temp에 저장
prev = i - 1 # 이전 위치 저장,
while (prev >= 0) and (arr[prev] > temp): # 이전 위치가 음수가 되지않고, 이전위치의 값이 선택한 값보다 크다면,
arr[prev + 1] = arr[prev] # swap
prev -= 1 # prev 감소
arr[prev + 1] = temp # 반복분이 끝난 뒤, prev에는 현재 temp값보다 작은 값들 중 가장 큰 값의 위치를 저장하고 있음.
# prev + 1에 temp의 값을 할당.
print(arr)
arr = [1, 3, 2, 6, 9, 7, 4, 5]
insertionSort(arr)
# 모두 정렬되어 있는 경우(optimal) 한번씩만 비교를 하므로 O(n)의 시간복잡도를 가진다.
# selection sort와 insertion sort의 차이
# k번째 반복 이후 첫번째 k 요소가 정렬된 순서로 온다는 점에서 유사,
# ss는 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지먼,
# is는 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만을 탐색하기 때문에
# 훨씬 효율적이다.
(1) 7 5 1 4 3
5부터 시작,
7과 5를 비교해 5가 더 작으므로 7을 한칸 뒤로 옮기고 그 자리에 5를 삽입한다.
(2) 5 7 1 4 3
세번째 원소 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한칸 뒤로 옮긴다.
그 앞의 원소 5와 1을 비교해 1이 더 작으므로 5를 한칸 뒤로 밀고 1을 그 자리에 삽입한다.
...반복...
결과 : 1 3 4 5 7
persistently