Insertion Sort : In non increasing format

Here is the pseudo code for arranging number in non increasing format using Insertion sort. This is one of the exercise of Book Introduction to Algorithms by CLRS.

//N is array's length
for j = N-1 to 1
   key = A[j];
   i = j + 1;
 
   while i<=N && A[i] > key
            A[i-1] = A[i];
            i = i +1;
   A[i-1] = key;

Input : 5 4 3 2 6
Output : 5 4 3 6 2
              5 4 6 3 2
              5 6 4 3 2
              6 5 4 3 2 [Final]

Notes on Insertion Sort

Insertion Sort is a way of sorting elements. While using insertion sort, we traverse from right to left element.

Steps :

1. Assume 0th element is already sorted.
2. Starting i from first element till last :
              -  In a loop(j ), check if the previous element is greater than the comparing element( for example for first time, we will be comparing 1st element to 0th element.)
              - If previous element is greater than comparing element, we will replace the j+1th element with j.[Remember before doing this keep array[i] stored in some variable, as it will be compared to all elements].
              - when loops finished, just replace the last index element with array[i] stored value.


Code :

for(i =1; i{
        int val = arr[i];
        int j = i-1;

        while( j >=0 && A[j] > val)
         {
              A[j+1] = A[j];
              j--;
         }
     
         A[j] = val;
}