Insertion Sorting Algorithm.

1. 선택정렬과 함께 가장 많이 사용되는 정렬방식으로 선택정렬이 많은 비교와 적은 교환으로 특정 지워진다면, 삽입정렬은 반대로 적은 비교와 많은 교환으로 특정 지워진다.

2. 이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적 수행.

3. i, j를 셋팅하고, i변수는 배열을 순서대로 카운트 한다. j변수는 i-1로 초기셋팅이 되어 i변수를 뒤에서 쫓아간다. i와 j변수가 각각 가리키고 있는 배열값을 비교하여 뒤에 있는 j변수 배열값이 i변수 배열값보다 크다면 i변수 배열값을 우측으로 옮기고, j값을 감소시킨다. while문을 사용하여 더이상 비교할 값이 없을때까지 비교하여, 모두 우측으로 이동하고 남는 자리에 처음에 비교대상이 되었던 값을 삽입하는 동작을 반복한다.

void insert_sort(int a[], int n)
{
int t, j;

for(int i=1; i<n; i++)
{
t = a[i];
j = i;

while(a[j-1] > t && j > 0)
{
a[j] = a[j-1];
j--;
}
a[j] = t;
}
}

삽입정렬은 입력자료에 굉장히 민감하다. 입력자료의 정렬된 정도에 따라 효율이 좋을 수도 있고 안 좋을 수도 있다.
그러나 삽입 정렬의 경우 작은 크기의 대충 정렬된 배열에 대해서는 제일의선택이 된다.

위 알고리즘을 개선하는 것은 어렵지 않다.
만약, 삽입 정렬할 레코드의 키값이 일정한 범위 내에 있다면 아래 기법을 고려해 볼 만 하다. 예를 들어 키값이 정수값인데 양의 정수만 다룬다면 이 배열의 제일 첫 요소 a[0]에 -1과 같은 값을 집어넣는다.
그리고, 실제의 자료들은 a[1] 이후에 저장하도록 한다.

그렇다면 다음의 insert_sort_1()함수와 같이 while루프의 판단문에서 j > 0과 같은 비교문을 하나 없앨 수 있다.

void insert_sort_1(int a[], int n)
{
int j, t;
for (i = 2; i<=n; i++)
{
t = a[2];
j = i;
while (a[j-1] > t) // j > 0이 없어졌다.
{
a[j] = a[j-1];
j--;
}
a[j] = t;
}
}

j > 0 이 없어진 것과 i의 변동 범위가 달라진 것 외에는 초기 함수와 다른 것이 없다.
a[0]는 루프의 경계를 벗어남을 방지하는 보초(sentinel)이다. a[0]에는 -1이 들어있고, 배열에는 양의 정수만 들어 있으므로, 예를 들어 가장 작은 수 1이 삽입될 곳을 찾기 위해 j값이 줄어든다 해도 a[0]의 값 -1보다는 1이 크므로 -1 뒤에 1이 삽입된다.

이렇게 a[0]는 경계의 벗어남을 막아주며, 또한 j > 0와 같은 비교문을 하나 없앰으로 인하여 N이 클 경우 이 기법의 효과는 두드러진다.