[정렬] insertion sort

insertion sort는 카드 게임을 할 때 우리가 카드를 정렬하는 방식과 굉장히 유사하다.

하나의 카드를 잡아서, 왼쪽부터 훑어나가면서 카드를 원하는 위치에 쏙 하고 집어넣기 때문이다.

다만 실제 구현에서는, 리스트에서 원소를 밀어주는 것이 꽤나 부담스럽게 다가온다.

 

0. i=1일 때,

arr[1]은 이미 정렬된 상태이다.

 

1. i=2일 때,

key = arr[2]

key를 arr[1]과 비교하여 올바른 위치에 넣되, arr[1] 자리에 들어가야 한다면 원래 arr[1]을 뒤로 밀어낸다.

이 때 arr[0]까지 갈 수도 있다.

올바른 위치에 넣는다는 것은, arr[j]가 arr[i]보다 작을 때, 밀어내기를 중단하는 것이다.

arr[0]~arr[i-1]은 이미 정렬된 리스트이지만 key는 완전히 새로운 원소이기 때문이다.

 

2. 반복

arr[i]를 arr[j = i-1 ~ 0]까지 비교하며 밀어낸다.

i가 마지막 원소일 때까지 반복한다.

 

시간복잡도

최선의 경우

원소 간 교체는 전혀 이루어지지 않고 key와 arr[i-1]의 비교 1회씩만 발생한다.

Best T(n) = 쎄타(n-1) = O(n)

 

최악의 경우: 역순으로 정렬된 리스트일 경우이다.

모든 i(n-1개)에 대해서 arr[0]까지의 비교, 이동이 각각 1회씩 발생한다.

바깥쪽 for문은 i=1부터 n-1까지 n-1번 돌고, 안쪽 for문은 j=i부터 1까지 2번씩 2i번 돈다.

2(1+2+...+n-1) = 2(n(n-1)/2) = n(n-1) = O(n^2)

 

def insertion_sort(arr):
    if len(arr) <= 1: return arr

    length = len(arr)
    for i in range(1, length): # 삽입될 숫자의 인덱스
        key = arr[i] # 삽입될 숫자를 복사해 둔다.

        ### arr[0]~arr[i-1]은 정렬된 배열이다.
        ### arr[j]와 arr[j-1]을 맞바꾸어가면서 계속해서 j를 감소시킨다.
        ### 
        for j in range(i, 0, -1):
            if key >= arr[j-1]:
                break
            arr[j], arr[j-1] = arr[j-1], arr[j]
    
    return arr

arr = [9, 3, 3, 3, 2, 7, 4, 1, 1, 8, 5, 2, 2, 6, 1]
print(arr) # [9, 3, 3, 3, 2, 7, 4, 1, 1, 8, 5, 2, 2, 6, 1]
print(insertion_sort(arr)) # [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9]