Data Structure – Insertion sort algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

(The example code is written in C programming language)

1. An insertion sort visits each element of the array, in turn. As it visits a particular element, it scans the array from the beginning to end to determines where in that segment of the array the current value belongs.
2. It then inserts the current value in that location and shifts every element of the array to the right, up to the present location. It then goes on to the next location (value) in the array.
3. Notice that one index is going from 0 to n and for each such value and another index is scanning the array from 0 to the value of the first index. The result of this is – that this type of sort is O(n2). Insertion sort is slower.

Example: C Program to sort n numbers using insertion sort.

#include
void insertion_sort(int a[],int n)
{
int i,j,item;
for(i=0;i<n;i++) { /* item to be inserted */ item = a[i]; /* Try from (i-1)th position */ j=i-1; while(j>=0 && item<a[j])
{
A[j+1] = a[j] /* Move the item to the next position */
j--; /* and update the position */
}
A[j+1]=item; /* appropriate position found and so insert item */
}
}
void main()
{
int i, n,a[20];
printf("Enter the no. of elements to sort n");
scanf("%d", &n);
printf("Enter n elements n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
insertion_sort(a,n);
printf("The sorted array is n");
for(i=0;i<n;i++)
printf("%dn",a[i]);
}