Insertion Sort is implemented by inserting a particular element at the appropriate position. The number of iterations used by this sorting technique depends on the number of items in the array. In general, if there are n items in the array, then (n-1) iterations are used. Here, we are going to implement this algorithm using C. In C, the array index starts from 0.
2) Assume that there are n elements in the list of items to be sorted.
3) Set i=1,j=0.
4) Compare the element at the ith position and the element at the jth position.
a) If a[i] is greater than a[j] do the steps (i),(ii),(iii)
iii) Check if shifting is required. If so, do steps Ò
Ò f (k is greater than j do step ►
► go to Step (a)
if(j<1) go to Step (a)
if(i<=n-1) go to Step (a)
5) Print the elements in the array a
During the first iteration, the element at the 1st position is compared with the element at the 0th position. During the second iteration, the element at the 2nd position is compared with elements at the 0th and 1st positions. This process is repeated for all the elements in the array up to (n-1)st iteration. This method is widely used by card players.
Corresponding C program
#include<stdio.h> //Header Files
void isort(int a,int);
printf("Enter Total nos:");
printf("\nEnter the Items 1 by 1:");
void isort(int x,int n)
printf("The Sorted Numbers are:\n");
Complexity The complexity of the insertion sort algorithm is shown in the following table.
|Algorithm||Worst case||Average case||Best case|
|Insertion sort|| O(n2)|| O(n2)|| O(n-1)|