a. 인덱스 1부터 끝까지 반복할 것이다.
b. 2와 4를 비교
- 2가 작기때문에 4 앞에위치 [ 2, 4, 7, 1, 3 ]
c. 7과 4를 비교
- 4가 작기 때문에 그대로 [ 2, 4, 7, 1, 3 ]
d. 1과 7을 비교
- 1이 작기 때문에 7 앞으로 이동 [ 2, 4, 1, 7, 3]
- 1이 4보다 작기 때문에 4 앞으로 이동 [ 2, 1, 4, 7, 3 ]
- 1이 2보다 작기 때문에 2 앞으로 이동 [ 1, 2, 4, 7, 3 ]
e. 3과 7을 비교
- 3이 작기 때문에 7 앞으로 이동 [ 1, 2, 4, 3, 7 ]
- 3이 4보다 작기 때문에 4 앞으로 이동 [ 1, 2, 3, 4, 7 ]
f. 정렬 할 것이 없기 때문에 종료
즉, 인덱스 1부터 끝까지 반복하는데,
각 인덱스보다 앞에있는 값들을 전부 비교해서 정렬한다.
import time
import numpy as np
def insertion_sort(data):
for idx in range(1, len(data)):
tmp = data[idx]
position = idx - 1
while position >= 0:
if tmp < data[position]:
data[position + 1] = data[position]
position -= 1
else:
break
data[position + 1] = tmp
return data
# 1~20 중 중복 없이 10개 숫자 추출
t1 = time.time()
data = np.random.choice(range(1, 20), 10, replace=False)
result = insertion_sort(data)
t2 = time.time()
print(result)
print(f"실행시간 : {t2 - t1:.8f}")