[자료구조] 삽입 정렬(insert sort)...

삽입 정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 삽입 정렬에서는 정렬할 자료가 두 개의 부분집합 S와 U로 나뉘어 있다고 생각하면 이해가 쉽다. 
 앞부분 원소부터 정렬을 수행하는데, 정렬된 앞부분의 원소들은 부분집합 S가되고, 아직 정렬되지 않은 나머지 원소들은 부분집합 U가 된다. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하여 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 줄인다.
 U의 원소를 모두 삽입하여 공집합이 되면 삽입 정렬이 완성된다.

n개의 자료를 정렬하는 삽입 정렬에서 사용하는 메모리 공간은 n개가 된다. 삽입 정렬에서 원소들을 비교하는 횟수가 최소인 경우는 이미 원소들이 정렬되어 있는 경우다. 이미 정렬되어 있는 경우에는 바로 앞자리 원소와 비교하는 연산이 한번만 필요하다.
 따라서 최소의 비교 횟수는 n-1이 되어 시간 복잡도가 O(n)이 된다. 그리고 모든 원소가 역순으로 되어 있는 경우에는 비교 횟수가 최대가 되어 시간 복잡도가 O(n²)가 된다.

 따라서 삽입 정렬의 평균 시간 복잡도는 O(n²)이 된다.

다음은 간단한 삽입정렬 알고리즘이다..

void insertSort(int a[], int n)
{
 int j, temp ;
 for(int i = 0 ; i < n ; ++i )
 {
  temp = a[i] ;
  j = i ;
  while ((j>0) && (a[j-1]>temp))
  {
   a[j] = a[j-1] ;
   j = j-1 ;
  }
  a[j] = temp ;
 }
}

그리고 다음은 삽입정렬에 대해서 쉽게 이해할 수 있는 동영상이다.