삽입 정렬(insertion sort) 알고리즘

1. 삽입 정렬?

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

2. 패턴 찾기

• 처음은 항상 인덱스(0)+1 에서 시작
• data_list = [9, 3, 2, 5]
  • 1회 : key 값 (9) , 인덱스(0) -1 보다 작으므로 => [9,3,2,5]
  • 2회 : key 값 (3) , key -1 값(9) 이 3보다 작으므로 => [3,9,2,5]
  • 3회 : key 값(2) , key -1 값(9) 보다 작고 -> key -2 값(2) 이 더 작으므로 => [2,3,9,5]
  • 4회 : key 값(5), 9보다 작고, 3보다 크므로 => [2,3,5,9]

1. for stand in range(len(data_list)) 로 반복
2. key = data_list[stand]
3. for num in range(stand, 0, -1) 반복
    - 내부 반복문 안에서 data_list[stand] < data_list[num - 1] 이면,
    - data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]

 

3. 알고리즘

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

import random

data_list = random.sample(range(20), 10)
print (insertion_sort(data_list))

>>[0, 3, 4, 5, 11, 12, 14, 17, 18, 19]

 

rand_data_list = [3, 5, 1, 2]

def insertion_sort(data_list):
    for stand in range(len(data_list)):
        key = data_list[stand]
        for num in range(stand, 0, -1):
            if key < data_list[num - 1]:
                data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]
            else:
                break
    return data_list

print (insertion_sort(rand_data_list))

 

4. 알고리즘 분석

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