[알고리즘] 삽입 정렬 알고리즘

삽입 정렬 알고리즘은 카드놀이를 할 때 손에 들고 있는 카드를 정렬하는 것과 유사합니다.

삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서

새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다.

예를 들어, 다음과 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다.

[2, 1, 5, 4, 3]

맨 처음에는 첫번째 2개의 값만 정렬 범위에 포함시키고 생각해보겠습니다.

앞에 있는 값 2는 뒤에 있는 값 1보다 작기 때문에 서로 자리를 바꿔줍니다.

[2, 1]: 2 > 1 => swap
 ^  ^
[1, 2]
 *  *

그 다음에는 기존의 정렬 범위에 한칸 확장하여 세번째 값을 추가시키고 생각해보겠습니다. 기존 정렬 범위에서 가장 큰 값인 2와 새롭게 추가된 5를 비교하면 자리를 바꿀 필요가 없다는 것을 알 수 있습니다. 기존에 정렬 범위에 있던 두 개의 값은 이 전 패스에서 이미 정렬이 되어 있기 때문에 굳이 1과 5를 비교할 필요는 없습니다.

[1, 2, 5]: 2 < 5 => OK
    ^  ^
[1, 2, 5]
 *  *  *

다음 패스에서는 정렬 범위를 한 칸 더 확장하여 4번째 값을 추가시키고 생각해볼 차례입니다. 기존 정렬 범위에서 가장 큰 값인 5와 새롭게 추가된 4를 비교하면, 앞에 있는 값이 뒤에 있는 값보다 크기 때문에 서로 자리를 바꿔야 합니다. 이제 기존 정렬 범위에서 두 번째로 큰 값인 2와 방금 자리를 교체 당한 4를 비교해보면 더 이상 자리를 바꿀 필요가 없다는 것을 알 수 있습니다.

[1, 2, 5, 4]: 5 > 4 => swap
       ^  ^
[1, 2, 4, 5]: 2 < 4 => OK
    ^  ^
[1, 2, 4, 5]
 *  *  *  *

마지막 패스에서는 정렬 범위를 전체로 확장하여 마지막 값까지 포함시킵니다. 여태까지 했던 방식과 동일하게 새로 추가된 값과 기존에 있던 값들을 뒤에서 부터 비교해나가면 2번의 자리 교체가 필요하다는 것을 알 수 있습니다.

[1, 2, 4, 5, 3]: 5 > 3 => swap
          ^  ^
[1, 2, 4, 3, 5]: 4 > 3 => swap
       ^  ^
[1, 2, 3, 4, 5]: 2 < 3 => OK
    ^  ^
[1, 2, 3, 4, 5]
 *  *  *  *  *

알고리즘 특징

• 선택/거품 정렬은 패스가 거듭될 수록 탐색 범위가 줄어드는 반면에 삽입 정렬은 오히려 점점 정렬 범위가 넚어집니다.
• 큰 크림에서 보았을 때 바깥 쪽 루프는 순방향, 안 쪽 루프는 역방향으로 진행하고 있습니다.

복잡도 분석

• 삽입 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
• 시간 복잡도는 우선 루프문을 통해 정렬 범위를 2개로 시작해서 전체로 확장해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 각 패스에서는 정렬 범위에 새롭게 추가된 값과 기존 값들의 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요하게 됩니다. 따라서 삽입 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
• 아래에서 다룰 최적화를 통해서 부분적으로 정렬된 배열에 대해서 성능을 대폭 개선할 수 있으며, 특히 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있습니다.

구현

두 개의 반복문이 필요합니다. 내부 반복문에서는 정렬 범위에 새롭게 추가된 값과 기존 값들을 뒤에서 부터 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 자리 교대(swap)를 합니다. 외부 반복문에서는 정렬 범위를 2에서 N으로 확대해 나갑니다.

ADL 코드

insertionSort(a[],n)
for(i<-2;i<=n;i<=i+1) do {
	v <- a[i]; // v는 임시 저장소
    j <- i;
    while (a[j-1] > v) do {
    	a[j] <- a[j-1]
        j <- j-1;
   }
   a[j] <- v;
end insertionSort()

 

Python 코드

def insertionSort(a,n):
	for i in range(2, n+1): // 두 번째 원소부터
    	v, j = a[i], i
    	while a[j-1] > v: 
    		a[j] = a[j-1] // a[j-1]을 오른쪽으로 한 자리 이동
  		    j -= 1
  		 a[j]=v // v를 빈자리에 삽입

 

 

O(N^2)의 시간 복잡도