삽입 정렬(insertion sort)

삽입 정렬(insertion sort)

1. 두 번째 인덱스부터 시작한다
2. 인덱스 앞의 데이터들과 비교한다
2-1. 앞의 데이터가 해당 인덱스의 데이터보다 작으면 둘의 위치를 바꾼다
3. 위 과정을 다음 나머지 값에서 반복한다

* 시간복잡도 : O(N^2) - 최선의 시간 복잡도: O(N)

import random


# set up
def insertion_sort1(data):
    for x in range(len(data) - 1):
        for y in range(x + 1, 0, -1):
            if data[y] < data[y - 1]:
                data[y - 1], data[y] = data[y], data[y - 1]
            else:
                break
    return data


def insertion_sort2(data):
    for i in range(len(data) - 1):
        j = i
        while j > 0 and data[j - 1] > data[j]:
            data[j - 1], data[j] = data[j], data[j - 1]
            j -= 1
    return data


# given
data = random.sample(range(30), 5)

# when
print(insertion_sort1(data))  # 3, 8, 10, 25, 28
print()
print(insertion_sort2(data))  # 3, 8, 10, 25, 28

   - 출처 : fastcampus