Insertion Sort

For each value of I between 2 and N, we start with A[1..I-1]already sorted,
and we sift(choose) A[I] down into its proper position, thus leaving A[1..i] sorted.
The sifting is accomplihed in aright-to-left scan starting at position I.

INSERTION SORT ANIMATION PAGE

STATIC SORT FOR INSERTION SORT

PROGRAM WRITTEN IN C++ FOR INSERTION SORT

#include<iostream.h>
#include<string.h>
#include<conio.h>

void insertion( int A[], int n);

main()
{

     int A[10],n,no;
 
     cout << " Input n:  " ;
     cin >> n;
     cout << "\n Input number :  ";
 
    for(int i=0;i<n;i++)
    {     cin >>no;
          A[i]=no;
     }
 
    insertion(A,n);
    return 0;

}

void insertion( int A[], int n)
{       int i,k,y,j,iteration=0;

     // initially A[0] may be thought of as a sorted file of
     // one element. After each repetition of the following
     // loop the elements A[0] through A[k] are in order
 

         for (k=1; k <n; k++)
         {
          // Insert A[k] into the sorted file

              y=A[k];

          // Move down 1 position all elements greater than y

          for( i=k-1; i>=0 && y < A[i];i--)
                 A[i+1]=A[i];

          // Insert y at proper position
                  A[i+1]=y;

     } // end for
} // end insertion