삽입정렬 - 알고리즘

 

Insertion Sort

삽입정렬은 이름에서 알 수 있듯이 삽입을 통해 정렬을 완성하는 알고리즘이다. 삽입정렬은 모든 데이터를 앞에서부터 차례로 비교 하여 자신의 위치에 삽입을 통해 정렬을 수행한다. 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다.

삽입정렬의 과정을 살펴보면 다음과 같다.

다음은 삽입정렬을 구현한 예이다.

#using C
void insertionSort(int list[], int n)
{
          int i, j, key;
          for(i=1; i<n; i++) {
                    key = list[i];  // 두 번째 값부터 선택
                    for(j=i-1; j>=0 && list[j]>key; j--)  // 선택된 값(key)보다 작은 값을 찾는다.
                              list[j+1] = list[j];       // 작은 값을 찾은 경우 그 값뒤의 모든 값을 우측으로 이동
                    list[j+1] = key;       // 해당되는 곳에 값을 삽입한다.
          }
}

삽입정렬 또한 비교연산을 상수로 보고 주어진 데이터가 정렬되어 있지 않다고 보면 O(n²)의 시간복잡도를 가진다. 삽입정렬의 특징은 시간복잡도가 입력 자료의 구성에 따라 달라진다는 사실이다. 입력 자료가 정렬되어 있으면 있을 수록 빨라진다. 따라서, 같은 시간복잡도를 가지는 선택정렬이나 버블정렬보다 효율이 높다.

삽입정렬은 또한 안정한 정렬방법이며 제자리 정렬(in-place sort)이다. 안정한 정렬이라는 것은 같은 값일 경우 상대적 위치가 바뀌지 않는 경우이다. 제자리 정렬은 정렬을 위해서 주어진 자료 공간 이외의 공간을 사용하지 않고 정렬하는 것을 말한다.


Reference : http://ko.wikipedia.org/
                 Data Structures in C, 생능출판사

출처 : http://proneer.tistory.com/entry/Sort-삽입-정렬Insertion-Sort