Wednesday, May 28, 2014

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;
}

No comments: