(3) 삽입 정렬법(Insertion Sorting)

 삽입 정렬 방법도 n개의 킷값에  대하여 n-1단계로 나누어져 수행된다.  버블 정렬과 다른 점은
i번째 단계에서는 앞에서부터 i개의 키가 이미 정렬되어 있으며 i+1번째 위치에 있는 키를 삽입키
로 하여 삽입키 앞에 있는 키들과 비교를 수행한다는 것이다. 이 과정에서 i+1번째있는 삽입키는
자신보다 작은 키값을 발견할 때까지 앞에 있는 키들을 차례로 비교하여  자신보다 큰 키들을 뒤
로 이동시킨다. 그러면 다음과 같은 예를 생각해 보자.



 위에서 삽입키 5앞에 있는 4개의 키를 포함하는 리스트는 이미 정렬되어 있으며  키값 5는 8과
비교하여 8이 크므로 8을 뒤로 이동하고, 다음으로  7과 비교하여 7이 크므로 7을 뒤로  이동한다.
다음에 4와 비교할 때 4가 5보다 작으므로 비교하는 것을 멈추고 4다음 위치에 5를 두면, 2, 4, 5,
7, 8의 5개의 키값을 갖는 리스트가 정렬된다. 따라서 삽입 정렬에서 이러한 단계를  n-1번 반복
하면 전체 리스트의 정렬이 완료된다.

 삽입 정렬에서 삽입키가 정렬된 리스트의 첫  원소보다 더 작은 경우에는 리스트의 범위  밖의 원
소와 비교를 시도할 수 있으므로 이를 방지하기 위하여 프로그램 작성시 항상 비교되는 키가 리스
트의 첫 원소인가를 확인하는 루틴을 포함시켜야 한다. 이러한 비교를 수행하는 대신 리스트의 맨
앞에 아주 작은 값 -∞름 먼저 저장하고 삽입 정렬을 수행하면 이러한 비교에 따른 시간 지체를
줄일수 있다. 보조 공간에 -∞를 먼저 저장한 후 정렬을 수행하는 예는 그림 5와 같이 나타낼 수
있다.



 이러한 과정을 C 프로그램으로 나타내면 리스트 8과 같다.

(리스트 8) 삽입 정렬
#define      MAXINT    30000

void Insertion(int n)
{
        int i,j,r;
        key[0]=-MAXINT;
        for (i=2;i<=n;i++)
        {
                j=i-1;
                r=key[i];
                while (r<key[j])
                {
                        key[j+1]=key[j];
                        j=j-1;
                }
                key[j+1]=r;
        }
}

삽입 정렬의 분석
 리스트 8의 Insertion에서 최악의 경우는 매단계에서 삽입하려는 킷값과 앞에 정렬된 리스트의
모든 키값들을 비교해야 할 때이며 다음과 같이 키값이 역순으로 입력된 경우가 최악의 경우에
해당한다.

 따라서 최악의 경우, 연산 시간은 다음의 계산에 의하여 O(n2)으로 표시된다.