# 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

- 1) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms (Third Edition). MIT Press, 2009. Chapter 2: Getting Started, p. 18