삽입 정렬(Insertion Sort)

삽입 정렬을 소개할 때 하는 설명들이 있다. 카드를 정렬하는 방법과 비슷하다.

예를 들어 원카드를 한다 생각해보자

패에 내 카드 5장이 들어있다. 모양은 모두 스페이스고, J K 3 9 7  로 구성되어있다. 이러면 어떻게 패를 정리할 것인가?

보통은 3을 하나 뽑고 맨 앞으로 놓는다. 그러면 3 J K 9 7 이 된다. 이런 식으로 정렬되는 것이 삽입 정렬이다.

이에 대한 ADL은 다음과 같다.

insertSort(a[],n)
	for (i <- 2; i<= n; i <- i+1) do {
    	v <- a[i];
        j <- i;
        while (a[j-1] > v) do {
        	a[j] <- a[j-1];
            j <- j-1;
        }
        a[j] <- v;
    }
end insertSort()

 

이를 간단한 예시를 통해서 정렬 수행 과정을 보이겠다. [3,2,5,1,4]

카드를 뽑아서 앞에  놓는다는 것은 기존에 있는 것을 미는 것이다. 따라서 이 원리를 그대로 적용한다.

삽입 정렬의 시간 복잡도는 \( O(N^{2} \) 이다.

python code는 다음과 같다.

def insertSort(a,n):
    for i in range(2,n+1):
        v = a[i]
        j = i
        while (a[j-1] > v):
            print(f'j = {j}')
            a[j] = a[j-1]
            j = j-1
            
        a[j] = v
        print(f'중간과정 {i} : ',a)
    return a

a = [-1,3,2,5,1,4]
print(insertSort(a, len(a)-1))