Array C++ Insertion Sort

Insertion Sort is a sorting technique based on the idea of inserting a new element in a set of given elements so that the resulting elements are also in sorted order. Suppose a set of 4 elements A[0], A[l], A[2], A[3] are to be sorted in ascending order. Initially sort A[0]and A[l] in ascending order. If A[l] is less than A[0], interchange their positions. Otherwise the positions of the elements remain the same. Next insert A[2] in the appropriate position so that the resulting array A[0], A[l] and A[2] remain sorted. The process is repeated in this manner.

Example

The program illustrates sorting numbers in ascending order using Insertion sort.

#include <iostream.h>
 const int n=5;
 void main() {
 int a[n], i,j,k;
 int temp;
 cout<<"enter the values "<<"\n";
 for(i=0;i<n;i++)
   cin>>a[i];
   for(j=1;j<n;j++) {
     for(k=0;k<j;k++) {
       if (a[j]<a[k]) {
         temp=a[j];
         for(int l=j;l>k;l--)
            a[l]=a[l-1];
            a[k]=temp;
            break;
       }
}
    cout<<"pass "<<j<<" ";
      for(i=0;i<n;i++)
        cout<<a[i]<<" ";
        cout<<endl;
}}

The first j elements are sorted where j =2,3 … upto n. The place where (j+1) th element is to be inserted ,that is k, is found .The elements between places k and j are shifted by one position. After that the (j+l)th element is inserted at the kth position.

Input and Output:

enter the values

34        22        49        10        2

pass     1          22        34        49        10        2

pass     2          22        34        49        10        2

pass     3          10        22        34        49        2

pass     4          2          10        22        34        49