Insertion sort (삽입 정렬)

ascending order로 정렬하는 qseudocode는 다음과 같다.

(index가 1부터 n까지라고 가정했을 때)

INSERTION-SORT(A, n) -> A[1 .. n]
for j <- 2 to n
	do key <- A[j]
    	i <- j-1
		while i > 0 and A[i] > key
        	do A[i+1] <- A[i]
            	i <- i-1
        A[i+1] = key

 

python 코드

위의 qseudo code를 python으로 짠 코드는 다음과 같다. (인덱스는 원래대로 0부터)

def insertion_sort(A):
    n = len(A)  # 리스트의 길이 계산
    for j in range(1, n):  # 두번째부터 배열의 마지막 요소까지
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key

# 테스트
lst = [5, 3, 2, 4, 1]
insertion_sort(lst)
print(lst)

그림으로 생각한다면, 

key값의 원래 위치에 더 작은 값을 넣고,

빈공간을 놔두며 한 칸씩 밀다가

A[i+1]에 key값을 다시 대입하게 되는 것이다.  

 

 

Loop invariant (루프 불변성)

알고리즘에서는 항상 올바른 값을 도출하는지를 확인해야 한다.

알고리즘의 중요한 파트가 반복문이라면, 그 부분을 Loop invariants(루프 불변성)을 통해 증명할 수 있다.

반복하는 동안 불변하는 state가 무엇인지 파악하고, Initialization, Maintenance, Termination으로 나눠서 state가 유지되는지 파악한다.

induction(귀납법)과 비슷한 형태의 증명이라고 볼 수 있다.

Maintenance 에서 특히 주의를 해야하는데, 일반적인 특정 숫자를 대입해보는 것이 아니라 k라면 k+1번째가 항상 성립하는지를 induction 증명과 같이 증명해야 한다. value 값이 아닌 index로 증명해야 하는 것이다.