[Programming/Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬은 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다. 하지만 전혀 다른 방법으로 정렬을 이뤄나간다.

삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘이다.

정렬된 상태로 삽입하기 위해서는 특정 위치를 비워야 하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야 한다. 

정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬 대상이다.

삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다.

삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 없다. 어차피 정렬된 영역에서 삽입의 위치를 찾는 것이니, 삽입위치를 찾으면서 삽입을 위한 공간의 마련을 병행할 수 있는 것이다.

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

void InsertSort(int arr[], int n) {
    int insData;
    int j;

    for (int i = 1; i < n; i++) {
        insData = arr[i];
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > insData) {
                arr[j + 1] = arr[j];
            }
            else {
                break;
            }
        }
        arr[j + 1] = insData;
    }
}

int main() {
    int arr[5] = { 5, 3, 4, 2, 1 };
    int n = sizeof(arr) / sizeof(int);

    InsertSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

1 2 3 4 5

*/

---

삽입 정렬(Insertion Sort): 성능평가

삽입 정렬은 정렬대상의 대부분이 이미 정렬되어 있는 경우 매우 빠르게 동작한다. 그럼 삽입 정렬의 성능평가를 위해 다음 반복문을 살펴보자.

for(int i=0; i<n; i){
  ...
  for(j=i-1; j>=0; j--){
    if(arr[j] > insData){ // 데이터간 비교연산
      arr[j+1] = arr[j]; // 데이터 이동의 핵심연산
    }
    else{
      break;
    }
  }
  ...
}

정렬대상이 완전히 정렬된 상태라면, 안쪽 for문의 if...else 문의 조건은 항상 '거짓'이 되어 break문을 실행하게 된다. 따라서 데이터의 이동도 발생하지 않고 if...else 문의 조건비교도 바깥쪽 for문의 반복횟수 이상 진행되지 않는다.

하지만 최악의 경우를 고려하면, 이 역시 버블정렬과 선택정렬과 다를 바 없다. 최악의 경우 안쪽 for문의 if...else 문의 조건은 항상 '참'이 되어 break문을 단 한 번도 실행하지 않는다. 따라서 바깥쪽 for문의 반복횟수와 안쪽 for문의 반복횟수를 곱한 수만큼 비교연산도, 이동연산도 진행이 되므로, 이를 근거로 비교연산과 이동연산에 대한 빅-오가 다음과 같음을 쉽게 추측할 수 있다.

O(n의 2제곱)

이러한 추측이 만족스럽지 않다면 다음과 같이 안쪽 for문에 속한 if...else문의 실행횟수에 대한 식을 세워서 정확히 계산을 진행하면 된다.

1 + 2 + 3 + ... + (n-2) + (n-1)