key
라고 하자)보다 앞의 원소(front_num
이라고 하자)의 값이 작은 경우, 현재 위치가 해당 key
의 삽입 위치이므로 순회를 종료한다. (왜냐하면 front_num
앞은 이미 정렬이 완성되어 있는 상태이기 때문이다.)
data[index]
이다. 각 index
에 대하여 해당 data[index]
의 삽입 위치를 찾기 까지의 과정을 1번의 턴이라고 정의하자.index
에 대하여 삽입 위치를 찾기 위해 해당 index
보다 앞의 원소들이 큰 지 작은 지 비교해야 한다.index2
를 사용했다. index2
의 범위는 (1 ~ index)이다. 왜냐하면 data[index2]
는 삽입하고자 하는 원소로 사용할 것이고, data[index2 - 1]
는 index
의 앞의 원소로 사용할 것이기 때문이다. data[index2 - 1]
는 index
의 앞 원소로, data[index2]
는 index
에 해당하는 원소로 사용한다.data[index2 - 1] > data[index2]
이면 앞 원소보다 현재 원소가 더 작은 경우이므로 두 원소의 자리를 바꾼다.data[index2 - 1] < data[index2]
이면 순회를 종료한다. 현재 위치가 해당 data[index2]
즉, data[index]
의 알맞은 삽입 위치이다.for index in range(len(data))
으로 반복for index2 in range(1 ~ index)
으로 반복data[index2 - 1] < data[index2]
이면 swap(data[index2 - 1], data[index])
data[index2 - 1] < data[index2]
가 아니면 더 이상 내부 반복문 순회 ❌def insertion_sort(data):
for index in range(len(data)):
for index2 in range(index, 0, -1): # index2는 (1 ~ index)까지
if data[index2] < data[index2 - 1]:
data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
else:
break
return data