<aside> 👉🏿 선택 정렬보다는 구현 난이도가 어렵지만 훨씬 효율적인 알고리즘이다.
특히 정렬의 정도에 따라 속도가 더 빠르다.
방법은 데이터를 하나씩 돌면서 첫번째 데이터는 이미 정렬되어있다고 가정,
다음 데이터부터 이전 데이터보다 작으면 앞쪽에 배치, 크면 그대로 두는 과정을 거친다.
</aside>
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 6을 받습니다.
4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
[4, 6, 2, 9, 1] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 2를 받습니다.
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
[2, 4, 6, 9, 1] 이렇게요!
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 9를 받습니다.
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
[2, 4, 6, 9, 1] 이렇게요!
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 1을 받습니다.
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
def insert_sort(list):
# 0번째 요소는 이미 정렬되어있다는 가정하에
# 1번째 요소부터 정렬 시작
for cur in range(1, len(list)):
# 1부터 cur까지 반복.
for delta in range(1, cur + 1):
# delta를 반복문 돌면서 1씩 증가시켜 역순으로 재정렬
cmp = cur - delta
# 현재값보다 다음 값이 크다면 스와핑
if list[cmp] > list[cmp + 1]:
list[cmp], list[cmp + 1] = list[cmp + 1], list[cmp]
else:
break
return list
print(insert_sort([4, 6, 2, 9, 1]))