알고리즘 | 삽입정렬(Insertion Sort) | 코드 설명

---

삽입정렬이란?

어떤 숫자 배열이 Input으로 들어왔을 때, 뒤죽박죽인 그 수열을 오름차순으로 정렬해나가는 과정을 거칩니다. 결국 Output은 "오름차순 수열"로 "정렬"됩니다. 

 

이때, 삽입정렬에서는 정렬시에 다음과 같은 방식을 따릅니다

 

"이미 정렬된 앞 원소들"과 "기준이 되는 수인 key"를 대소비교합니다. 그리고 key인 수를 "이미 정렬된 앞 수열"의 적절한 자리에 삽입합니다. 이때, 이미 정렬되어있는 앞 원소들과 key를 차례차례 대소비교해가며 삽입의 위치를 정합니다. 이러한 정렬 방식을 삽입정렬이라고 합니다.

 

 

예를 들어 3 8 5 2 1이라는 수열이 있다고 합시다.

왼쪽에서 오른쪽 방향으로 차례차례 수의 크기를 비교해나가며 정렬을 쭉 하게 됩니다. 어떤 수를 그 앞자리에 있는 수와 하나하나 크기비교하며 정렬하게 되는 거죠!

 

일단 첫번째 원소인 3을 볼까요? 3은 첫번째 원소라서 그 앞자리 원소는 존재하지 않습니다. 그래서 일단 '3'은 정렬된 상태라고 보고 시작합니다.

 

그 다음 8이라는 숫자를 기준으로 봅시다. 두번째 원소인 8은 그 앞의 첫번째 원소 3보다 큽니다. 그럼 정렬할 필요 없겠죠? 그냥 둡니다. 여기서 중요한 것은, "일단 3 8 까지는 정렬된 상태입니다"

 

세번째 원소인 5를 봅시다. (이때, 5를 key라 합니다.) 앞에 정렬된 상태로 존재하는 "3 8"의 원소들보다 큰지 작은지 비교해야 합니다. 일단, 5의 바로 앞에 있는 8보다 작습니다. 그럼 자리를 서로 바꿔야겠죠? 두번째 원소인 8을 다음자리로 밀어버립시다. key보다 8이 더 크니까요.

3  ㅁ  8  (8을 뒤로 민 상태)

그 다음은 3과 key를 비교합시다. 다행히 3이 key보다 더 작네요? 그럼 3은 뒷자리로 밀 필요 없이 거기 그대로 둡니다. 이런 크기비교에 따라서 3은 그대로 뒀고, 8은 뒤로 밀었으니까, 5라는 key는 그 사이에 두면 되겠네요. 그럼 3  5  8 로 정렬이 됩니다. 이 단계에서 만들어진 3 5 8은 역시 또 정렬된 상태를 유지합니다.

 

 

 

이런식으로 "key"와 "정렬되어있는앞수들"의 원소를 비교해나가며 key가 들어갈 자리를 정해갑니다. 이러한 정렬을 삽입정렬이라고 합니다.

 

 

 

 

중요한 전제

삽입정렬 알고리즘으로 기본적으로 전제하고 가는 것이 있습니다. "정렬된 상태를 유지하며 간다"라는 것입니다. 매 loop마다 변하지 않는 사실이죠. 루프 불변성으로 설명할 수 있습니다.

아까전부터 계속 강조하고 있는 개념이기도 합니다. 

 

Loop invariant (루프 불변성)

: 루프에서 항상 만족해야하는 성질입니다. 즉, 루프에서 계속 유지하며 가는 조건입니다. 루프 알고리즘의 정확도를 위해서는 항상 이 루프 불변성의 조건을 성립하고 있어야 합니다. 삽입정렬의 경우의 루프불변성은 다음과 같습니다.

 

-Initialization(루프실행전) : 루프가 시작하기 전에, 이미 첫번째 원소에 대해서는 정렬되어있습니다. 사실 첫번째 원소는 하나라서 비교할 것도 없죠. 정렬된 상태로 봅니다.

 

-Maintenance(루프실행중) : 정렬된 상태를 매 루프마다 항상 만족하고 있습니다.

 

-Termination(루프종료후) : 루프가 다 끝났을 때 정렬이 되어있습니다.

 

즉, 삽입정렬에서 기준이 되는 j번째 값인 A[j]를 key로 둔다면, A[1]부터 A[j-1]까지의 값들을 정렬된 상태를 계속 만족하고 있다는 것입니다. 참고로 지금 이 포스팅에서 1, 2, ..., j-1은 0부터시작하는 인덱스가 아니라 '번째'입니다. 첫번째 두번째.. j-1번째로 이해하시면 됩니다. 

 

---

코드로 확인하기

의사코드로 삽입정렬의 알고리즘을 확인해봅시다.

 

INSERTION-SORT(A)
  for j <- 2 to length[A]
    do key <- A[j]
       //Insert A[j] into the sorted sequence A[1 ... j-1]
       i <- j-1
       while i>0 and A[i]>key
         do A[i+1] <- A[i]
           i <- i-1
       A[i+1] <- key

 

 

위 코드는 배열A에 대해 다음 영상과 같이 동작합니다.

 

영상을 보시면 이해가 더 빠를 겁니다.

 

잠시 후에는 삽입정렬의 복잡도를 이야기해보겠습니다.