insertion sort 이해해보기

아래는 insertion sort의 코드이다

 

#insertion sort
def insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key: # key가 더 작으면 앞으로
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

selection sort가 어떤 위치에 들어갈 value를 뒤의 것들을 쭉 훑은 뒤에 '뽑아서' 가져오는 것이라고 한다면

insertion sort는 어떤 위치의 것을 그 앞 어디에 '넣을' 것인지 정하는 것이다.

위치를 정해야하는 value의 위치 i. value를 key에 저장하고 앞의 값들(위치 j)과 비교한다.

자신보다 더 큰 값을 마주한 경우, 그 값을 뒤로 한칸 미룬다(복사).

이를 자신보다 (같거나 더 작은 값)을 만나거나 또는 (j가 -1) 이 될 때까지 반복한다.

그리고 마지막 비교위치 j의 오른쪽에 key값을 저장한다. (-1인 경우 맨 앞, 그 외의 경우 자기보다 작은 값 오른쪽)

0번 위치의 경우 나머지들이 정렬이되면 자동으로 정렬되는 위치이다.(selection에서의 마지막위치 같다고 보면 됌.)