삽입 정렬

---

• 삽입 정렬은 두 번째 인덱스부터 시작한다.
• 인덱스 앞에 있는 데이터부터 비교해서 앞 데이터가 더 크면, 값을 바꾼다.
• 위의 과정을 데이터가 더 작을 때까지 반복한다.

시간 복잡도

• 반복문이 두 개 이므로 시간 복잡도는 $O(n^2)$이다.

구현

---

def InsertionSort(data_list):
    for i in range(len(data_list)-1):
        for j in range(i+1, 0, -1):
            if data_list[j] < data_list[j-1]:
                data_list[j], data_list[j-1] = data_list[j-1], data_list[j]
            else:
                break
    return data_list