Insertion sort Algorithm and Insertion Sort Program in C++

Insertion Sort :

Insertion sort algorithm is very popular with bridge players when they first sort their cards . In this procedure , we pick up a particular value and then insert it at the appropriate place in the sorted sub list , i.e during kth iteration the element a[k] is inserted in its proper place in the sorted sub array a[1] , a[2] , a[3].....a[k-1] . This task is accomplished by comparing a[k] with a[k-1] , a[k-2] , a[k-3] and so on until the first element a[j] such that a[j]<=a[k] is found . Then each of the elements a[k-1] , a[k-2] , .....,a[j+1] are moved one position up , and then element a[k] is inserted in (j+1)st position in the array .
        For more clarity , carefully examine the following steps,
Pass 1:a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted .
Pass 2:a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that the elements a[0] , a[1] , a[2] are sorted .
Pass 3:a[3] is inserted either before a[0] or between a[0] and a[1] or between a[1] and a[2] or after a[2] so that the elements a[0],a[1],a[2],a[3] are sorted .
.
.
.
Pass n-1:a[n-1] is inserted in proper place in the sorted subarray a[0],a[1],a[2],....,a[n-2] so that after insertion , the elements a[0],a[2],.....,a[n-1] are sorted .
Thus after (n-1) passes , the array will be sorted in ascending order . The various steps required to implement insertion sort are summarized in the algorithm given below ,

Also check : Algorithm for Depth First Search 

Algorithm for Insertion sort :

Insertionsort( a , n ) 

Begin
    for k=1 to (n-1) by 1 do
        Set temp=a[k]
        Set j=k-1
        while((temp<a and (j>=0)) do
            Set a[j+1]=a[j]
                Set j=j-1
        endwhile
            Set a[j+1]=temp
    endfor
End

          Here a is a linear array with n elements in memory . This algorithm sorts the elements in the ascending order . It uses a temporary variable temp to facilitate the exchange of two values and variable j and k are used as loop control and index variables .
The above algorithm moves the elements up by one position till the correct slot for the element is found and then inserts the element at that slot .

Also check : Algorithm and Program for Heap Sort

Example for Insertion Sort :

To Illustrate the working of the insertion sort method ,consider the following array a with 7 elements as 
35 , 20 , 40 , 100 , 3 , 10 , 15
Given array a ,

Pass 1

Pass 2 : Since a[1]<a[0], insert element a[1] before a[0] , giving the following array ,

Pass 3 : Since a[2]>a[1] , no action is performed .

Pass 4 : Since a[3]>a[2] , again no action is performed .

Pass 5 : Since a[4] is less than a[3] , a[2] ,a[1] as well as a[0] , therefore in insert a[4] before a[0] , giving the following array ,

Pass 6 : Since a[5] is less than a[4],a[3],a[2] and a[1] , therefore insert a[5] before a[1] ,giving the following array .

Pass 7 : Since a[6] is less than a[5],a[4],a[3], and a[2] , therefore insert a[6] before a[2] giving the following sorted array .

Analysis of Insertion sort :

Here we can see that the number of passes required to sort the list of eight elements are seven , hence N-1 pasees are required to sort the list of N elements using insertion sort . Insertion sort is considered to be useful for a small collection of data . Insertion sort takes fewer comparisons than the bubble sort , so it will normally take less time than the bubble sort . Insertion sort is very efficient for a small list of elements and it is slow when numbers of elements in a list are very large ,
1) Best Case : If the array is already sorted , no interchange will take place althrough we have to go through N-1 passes .Therefore the complexity in the best case is O(N-1)=O(N) .Therefore when the input data contains sorted list of elements then the insertion sort works slightly faster and so it is highly efficient .
2) Average case : If the elements are scattered in this list we need to insterchange them during comparisons . We assume that on an average there are (n-1)/2 interchanges and we have to go through N-1 passes to sort the list . Therefore the average case complexity is O(N^2).
3) Worst case : When the list is in the reverse order then each element inserted will be compared with previous N-1 elements in the sorted List and we have to go through the N-1 passes to sort the list . So the worst case complexity is O(N^2) .

Program for Insertion Sort in C ,C++

#include<iostream.h>
#include<iomanip.h>
template<class T>
class Array 
{
    T *a;
    int size;
public :
    Array(int n)
    {
        size=n;
        a=new T[n];
    }
    ~Array()
    {
        delete a;
    }
    void inputarray();
    void outputarray();
    void insertionsort();
};
template<class T>
void Array<T>::inputarray()
{
    int i;
    cout<<"\n Enter "<<size<<"elements of array\n";
    for(i=0;i<size;i++)
    {
        cin>>a[i];
    }
}
template<class T>
void Array<T>::outputarray()
{
    int i;
    for(i-0;i<size;i++)
    {
        cout<<a[i]<<"\t";
    }
    cout<<endl;
}
//Sorting array elements with Insertion sort algorithm
template<class T>
void Array<T>::insertionsort()
{
    int k,temp,j;
    for(k=1,k<=size;k++)
    {
        temp=a[k];
        j=k-1;
        while((temp<a[j])&&(j>=0))
        {
            a[j+1]=a[j];
            j=j-1
        }
        a[j+1]=temp;
    }
}

Final Words :

If I had missed any concept in insertion , please get it to me through comments .