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. 

									
					$ ./a.out
					-4 1 1 2 3 9

With Array Input

To do away with the above pre-coded set of numbers, we do slight modifications to the above C program to read numbers dynamically. For this example, we assign the size of the array numbers[] to just 100, which of course can be designed better by using dynamic memory allocation. This of course is a separate discussion. 

					
					#include <stdio.h>
					int main() {
						int numbers[100], key, i, j, n;
						printf("Enter the dimension of the array: ");
						scanf("%d", &n);
						// array input
						for(i = 0; i < n; i++) {
							printf("Enter numbers[%d]: ", i);
							scanf("%d", &numbers[i]);
						}
						// 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;
					}

The worst and average-case complexity for performing an insertion sort is $\text{O}(n^{2})$, which is the same as that of Bubble Sort, but is observed to be much more efficient than it. The best-case time complexity is $\text{O}(n)$, which is on an already sorted array.

Notes