Insertion Sort

 

Description

 

♦  The insdertion sort is used for an array that is already sorted and another element is to be added. ♦  The insertion sort, unlike the other sorts, passes through the array only once. ♦  It is commonly compared to organizing a handful of playing cards. ♦  You pick up the random cards one at a time. ♦  As you pick up each card, you insert it into its correct position in your hand of organized cards.

♦  It works by making one pass through the array of values.

♦  No action is performed for elements that are in the correct order.

♦  When it encounters an element that is out of order, it goes back through the array to find the appropriate place for that element.

♦  In each case it stores the out of order element, replaces the cell in which it resides with the one behind it, then places the stored element

     (one that was out of order) into the cell behind, etc, until it finds the correct space,

 

♦  In the worst case, when the items are in reverse order, it will have to go back to the beginning of the array each time it considers an element.

     In that case, for the first element it will look at 0 previous values; for the second element, it will loop at  previous values etc

 

♦  So the time taken is proportional to

 

     0 + 1 + 2 + ... + (N-2) + (N - 1)

 

♦  This is, therefore, proportional to N², which is the order of insertion sort.

 

The algorithm

 

public class InsertionSort

{

  public static void main(String[] args)

  {

    int array[ ] = { 2,4,6,8,3 };

    System.out.println("The Original Array ");

    printArray(array);

    System.out.println();

    insertionSort(array);

    System.out.println("The Sorted Array ");

    printArray(array);

  }    

    public static void insertionSort(int array[])

    {

      for (int outer = 1; outer < array.length; outer++)

      {

        int position = outer;

        int key = array[position];                                            //Storing the element - see above explanation

        while (position > 0 && array[position - 1] > key)       //Does not execute if the elements are in correct order

        {

          array[position] = array[position - 1];                         //Swapping - same technique covered earlier

          position--;                                                                 //Backing up to find the correct position

        }

        array[position] = key;                                                 //Moving the out of order element backwards

      }

    }

    public static void printArray(int array[])

    {

       for (int k = 0; k< array.length; k++)

        {

          System.out.print(array[k] + " ");

        }

    }

}