삽입 정렬 알고리즘

예시 배열 - [9, 3, 2, 5]

 

1회차 - 1과 0을 비교 후 교체  [3, 9, 2, 5]
2회차 - 2와 1을 비교 후 교체 [3, 2, 9, 5], 1과 0을 비교 후 교체 [2, 3, 9, 5]
3회차 - 3과 2를 비교 후 교체 [2, 3, 5, 9], 2과 1를 비교 후 교체 [2, 3, 5, 9], 1과 0을 비교 후 교체 [2, 3, 5, 9]

 

턴 수 - length - 1

각 턴의 순회 횟수 - length - 1

 

비교 후 뒤에 값이 더 클 경우 반복문 종료

앞에 회차에서부터 거슬러오면서 정렬을 했기 때문에 비교 시 값이 더 큰 경우 앞에 값들은 이미 정렬된 값들이라는 확신을 할 수 있음

 

정리

1. length -1만큼 반복문

2. 1번 안에 index + 1(시작), 0(1 까지), -1만큼 중첩 반복문

3. 비교 후 앞의 값보다 더 작으면 바꿔주는 로직

4. else로 반복문 종료

 

def insertionSort(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