파이썬 알고리즘 - 삽입정렬

파이썬 알고리즘 - 삽입정렬

< 그림 위키피디아 - https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC >

내가 푼 방식

-> 모범 답안에 비해서 시간 복잡도가 높게 나왔다.

def insertion_sort(my_list):
    for i in range(1, len(my_list)):
        for i2 in range(0, i):
            if my_list[i] < my_list[i2]:
                small = i2
                break
            else:
                small = i

        if small != i:
            a = my_list[i]

            for j in range(i, small, -1):
                my_list[j] = my_list[j-1]
                my_list[j-1] = my_list[j-2]

            my_list[small] = a


some_list = [11, 3, 6, 4, 12, 1, 2]
insertion_sort(some_list)
print(some_list)

모범답안

# 삽입 정렬
def insertion_sort(my_list):
    for i in range(len(my_list)):
        key = my_list[i]

        # i - 1부터 시작해서 왼쪽으로 하나씩 확인
        # 왼쪽 끝까지(0번 인덱스) 다 봤거나
        # key가 들어갈 자리를 찾으면 끝냄
        j = i - 1
        while j >= 0 and my_list[j] > key:
            my_list[j + 1] = my_list[j]
            j = j - 1

        # key가 들어갈 자리에 삽입
        # 왼쪽 끝까지 가서 j가 -1이면 0번 인덱스에 key를 삽입
        my_list[j + 1] = key

some_list = [11, 3, 6, 4, 12, 1, 2]
insertion_sort(some_list)
print(some_list)