삽입 정렬 (insertion sort)

삽입 정렬(insertion sort)란
해당 인덱스(key 값) 앞에 있는 데이터(a)부터 비교해서 key 값이 더 적으면, a값을 뒤 index로 복사한다. 
이를 key 값이 더 큰 데이터를 만날 때까지 반복한다. 

예를 들어 data_list = [9, 3, 2, 5] 일 때 sorting을 해보자

• 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5]
• 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5]
• 세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5]
• 네 번째 실행하면, key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: [2, 3, 5, 9]

 

* 알고리즘 구현

#10개 랜덤 숫자로 구현

import random

list = random.sample(range(1, 100), 10)
print(list)

for idx in range(len(list) - 1):
    for j in range(idx + 1, 0, -1):
        if list[j] < list[j-1]:
            list[j], list[j-1] = list[j-1], list[j]
        else:
            break

print(list)

Result : [46, 59, 13, 51, 7, 8, 33, 19, 88, 63]

             ➞ [7, 8, 13, 19, 33, 46, 51, 59, 63, 88]

 

* 알고리즘 분석

반복문이 두 개 O(n²)
→ 최악의 경우, 𝑛 • (𝑛−1) / 2
→ 완전 정렬이 되어 있는 상태라면 최선은 O(n)