오늘도 활짝^_____^

  처음 i-1배열슬롯(slot)의 키들이 정렬되어 있다고 가정한다. x를 i번째 슬롯에 있는 키 값이라 하자. x와 (i-1)번째 슬롯에 있는 키, (i-2)번째 슬롯에 있는 키, …, 등등 차례로 비교하되, x보다 작은 키를 찾을 때까지 이를 계쏙한다. j를 그 키가 위치한 슬롯이라고 하자. (j+1)번째 슬롯에서 (i-1)번째 슬롯에 있는 키들을 (j+2)번째 슬롯에서 i번째 슬롯으로 옮기고(move), (j+1)번째 슬롯에 x를 삽입한다. 이 과정을 i=2에서부터 i=n까지 반복한다. 다음 그림에서 이 정렬을 잘 설명해 준다.

  삽입정렬의 알고리즘은 다음과 같다.

알고리즘) 삽입정렬 ------------------------------------------------------------

 * 문제 : 비내림차순으로 n개 키를 정렬.
 * 입력 : 양의 정수 n; 키의 배열 S(인덱스는 1부터 n)
 * 출력 : 비내림차순으로 정렬된 키들로 구성된 배열 S

 void insertionsort ( int n, keytype S[])
 {
    index i, j;
    keytype x;

    for( i = 2; i <= n; i++)

    {
        x = S[i];
        j = i - 1;

   
        whlie(j > 0 && S[j] > x)

        {
            S[j + 1] = S[j];
            j--;
        }

        S[j + 1] = x;
    }
 }

---------------------------------------------------------------------------

참고 : Foundations of Algorithm, using C++ Pseudocode - 3rd Edition