알고리즘 - 삽입 정렬

- insertion sort

- 오른쪽 리스트(정렬 안 된)에서 왼쪽 리스트(정렬 된)로 하나씩 자리를 찾아 삽입하면서 정렬

- 삽입을 위해 배열을 계속 이동시켜야 함

- 자료가 이미 정렬되어 있는 경우의 시간 복잡도 : 
  자료가 역순일 경우 최악의 복잡도 : 


- 코드

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    j = i;
    remember = data[j];
    while ( --j >= 0 && remember < data[j] )
        data[j+1] = data[j];
    data[j+1] = remember; 
  }
}