삽입 정렬(Insertion sort)

간단한 정렬 알고리즘 중 하나인 삽입 정렬에 대해서 알아보자.

 

삽입 정렬?

삽입 정렬이란 정렬이 되어있지 않은 부분의 데이터를 뽑아서 정렬된 부분의 적절한 위치에 삽입하는 방법이다.

즉, 배열에서 생각해보면 다음 그림과 같이 배열에서 정렬이 되지 않은 부분의 숫자를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복한다. 삽입 정렬은 추가적인 배열을 사용하지 않고 입력 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다.

삽입 정렬의 원리

정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 부분의 크기는 하나 커지게 되고, 정렬이 되지 않은 부분의 크기는 하나 줄어들게 된다. 이러한 삽입 연산을 정렬되지 않은 요소가 없을 때까지 반복하면 전체 리스트가 정렬된다.

삽입 정렬 과정

삽입 정렬 구현

#include <stdio.h>
#define MAX_SIZE 5

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {8, 5, 6, 2, 4};

  // 삽입 정렬 수행
  insertion_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

 

삽입 정렬의 시간 복잡도 분석

삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 먼저 입력 자료가 이미 정렬되어 있는 경우 가장 빠르다. 이때 삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교횟수는 n-1번, 총 이동횟수는 2(n-1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다.

최악의 경우는 입력 자료가 역으로 정렬된 경우이다. 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동하여야 한다. 따라서 외부 루프 안의 각 반복마다 i번의 비교가 수행되므로 총 비교횟수는 다음과 같다.

총 이동횟수는 외부 루프의 각 단계마다 i+2번의 이동이 이루어지므로 다음과 같다.

따라서 최악의 경우 삽입 정렬의 시간 복잡도는 O(n^2)이다.

 

삽입 정렬은 비교적 많은 레코드들의 이동을 포함한다. 결과적으로 삽입 정렬은 레코드 양이 많고 특히 레코드 크기가 클 경우 적합하지 않다. 반면에 알고리즘이 간단하므로 레코드의 수가 적을 경우 효과적일 수 있다. 특히, 삽입 정렬은 대부분의 레코드가 이미 정렬되어 있는 경우 효율적인 알고리즘이다.