삽입 정렬(Insertion Sort)

이전에 다룬 버블,선택정렬은 정렬이 되어있어도 무조건 위치를 바꾸는 방식이지만, 삽입 정렬은 필요할 때만 위치를 바꾼다
시간 복잡도 : O(N^2), 같은 시간 복잡도를 가지는 정렬 중에서는 가장 빠름

예제

먼저, 삽입 정렬은 첫 번째 요소인 1은 정렬되어 있다고 가정한다.

10은 1의 앞, 1과 10 사이 2군데 위치할 수 있지만 10이 1보다 크기 때문에 자리를 유지한다.
다음으로 5는 3군데 위치할 수 있으며, 1과 10사이에 삽입한다.
다음으로 8는 4군데 위치할 수 있으며, 5와 10사이에 삽입한다.
.
.
.

구현

github link

def insertion_sort(data):
    for i in range(1, len(data)):
        j = i-1
        while(j>=0 and data[i]<data[j]):
            j -= 1
        data.insert((j+1), data[i])
        del data[i+1]
    return data
    
def insertion_sort2(data):
    for i in range(1, len(data)):
        for j in range(i, 0, -1):
            if (data[j] < data[j-1]):
                data[j], data[j-1] = data[j-1], data[j]
            else:
                break
    return data

if __name__ == "__main__":
    data = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
    res = insertion_sort2(data)
    print('res: ', res)

먼저, 첫 번째 요소는 정렬되어 있다고 가정한다.
데이터 개수만큼 반복하면서 :
데이터 개수-1(n-1)만큼 반복하면서:
정렬할 j번째 요소를 정렬된 [0~(j-1)] 순서에 맞게 넣고, 삽입될 위치를 찾았다면 해당 위치에서부터 한 칸씩 뒤로 이동시킨다.

python insert()함수 : 원하는 위치에 값을 삽입하고, 삽입한 위치에서부터 한 칸씩 뒤로 이동시킴
a = [1, 2, 3]
a.insert(0, 4)
결과 : a는 [4, 1, 2, 3]

시간 복잡도

이중 for문을 사용하기 때문에 시간 복잡도가 O(N^2)이지만, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 O(N)의 시간 복잡도를 가진다.

References
나동빈 알고리즘 강의