Insertion sort algorithm iterates through the array sorting one element at a time. The array is split into two sub arrays as it iterates - one sub array contains the sorted elements and the other contains the unsorted items. This is exactly like sorting a set of playing cards where you pick up one card at a time and puts it in the right position.
The iteration starts by comparing the second element of the array to the first. If the second element is less than the first then the two elements are swapped.
In the next iteration, the third element is first compared to second element, if the third element is smaller then it is swapped with the second element. Then it is compared to the first element and swapped if smaller than the first.
In general, the element that is picked up is compared to each element before it until its correct position is located.
Insertion sort is a very efficient algorithm for sorting smaller arrays. It requires n-1 iterations to sort an array containing n elements. In the best case, the maximum number of comparisons required is the sum of n-1 numbers.
Here is a C program that takes the elements of an array as input, sort it using Insertion sort algorithm and prints the sorted array.
#include <stdio.h>
int main()
{
int myarray[50];
int i, j, n, temp;
/* Get number of elements in the array */
printf("Enter number of elements in the array \n");
scanf("%d", &n);
/* Read elements of the array */
printf("Enter the array elements \n");
for (i = 0; i < n; i++)
scanf("%d", &myarray[i]);
/* Sort elements of the array */
for (i = 1; i < n; i++) {
j = i;
while ( (j > 0) && (myarray[j-1] > myarray[j]) ) {
temp = myarray[j-1];
myarray[j-1] = myarray[j];
myarray[j] = temp;
j--;
}
}
/* Print the sorted array */
printf("Sorted Array\n");
for (i = 0; i < n; i++)
printf("%d \n", myarray[i]);
return 0;
}
