# C Program: Insertion Sort

Insertion sort is an efficient sorting algorithm for performing a sort on small number of elements.

This sorting algorithm is analogous to the way people sort playing cards. Consider a set of shuffled cards (numbers), placed faced down on the table. You pick each of them one by one, then insert them into your left hand at the correct position after comparing with the cards already you hold in your hand. How this comparison is perfomed is illustrated in the image below.

Consider the below set of unsorted numbers:

( 3 1 -4 2 9 1 )

In this image, we illustrate the use of Insertion Sort to sort them in ascending order.

The reordered numbers will finally result in the set being sorted as shown below.

( -4 1 1 2 3 9 )

Below is the pseudo-code for Insertion Sort we perfomed above. I have lifted it from the book Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.1 The given set of unsorted numbers is assigned to an array A.

				
for j = 2 to A.length
key ← A [j]
// Insert A[j] into the sorted sequence A[1 .. j-1]
i ← j – 1
while i > 0 and A[i] > key
A[i+1] ← A[i]
i ← i – 1
A[i+1] ← key



We implement the above pseudo-code into a C program.

We assign the set ( 3, 1, -4, 2, 9, 1 ) to the array numbers[], which is of type int. There is another important variable called key, which is assigned the unsorted number for each loop, starting from the second element.

				
#include <stdio.h>

int main() {
int numbers[] ={3, 1, -4, 2, 9, 1}, key, i, j, n;

// the size of given array
n = 6;

// insertion sort
for(j = 1; j < n; j++) {
key = numbers[j];
i = j - 1;

while (i >= 0 && numbers[i] > key) {
numbers[i + 1] = numbers[i];
i = i - 1;
}

numbers[i + 1] = key;
}

// printing the sorted array
for(i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}

return 0;
}



On compiling and executing the above program, we get the sorted numbers as follows.