3. 삽입 정렬

1. 삽입 정렬 이란

 - 데이터의 삽입을 통해 정렬하는 알고리즘

2. 삽입 정렬의 개념

 - 손안의 카드를 정렬하는 방법과 유사

- 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리에 찾아 삽입

- 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드 정렬  

 - 두 번째 값부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 값을 삽입하여 정렬

 

3. 삽입 정렬

e = [6, 7, 2, 3, 6, 9, 1, 12, 45, 52]


def insertion_sort(d_list):
    for i in range(1, len(d_list)):
        value = d_list[i]
        while i > 0 and d_list[i - 1] > value:
            d_list[i] = d_list[i - 1]
            i -= 1
        d_list[i] = value
    return d_list


print(insertion_sort(e))

------------------------------------

[1, 2, 3, 6, 6, 7, 9, 12, 45, 52]