In Detail : A Simple Insertion Sort In Java Along With Generics Implementation

Insertion Sort :

    Insertion Sort is an elementary sorting algorithm. It is easy to understand and implement, but is unacceptably slow when there are multiple records to sort.

A Real Life Example Illustrating Insertion Sort :

    Imagine you have a stack of electricity bills from the past two years & you wish to sort them by date. A fairly natural way to do this might be look at the first two bills & put them in ascending order. Then take the third bill & put it into the right order with respect to the first two & so on.

As you take each bill, you would add it to the sorted pile that you have already made.

This naturally intuitive process is the inspiration for Insertion Sort.

How Insertion Sort Works ? 

    Insertion Sort starts iteration from second element of the input array/ list. In each iteration the current element is compared with its previous element & swaps, if the previous element is greater than the current element. The iteration terminates when the current element is greater than its previous element. So the 2nd element is compared with 1st element, and 3 rd element is compared with 2nd element & 1st element, 4th element is compared with 3rd, 2nd, 1st elements and so on.

The Algorithm : 

for i = 2:n,

    for (k = i; k > 1 and a[k] < a[k-1]; k--) 

        swap a[k,k-1]   

end 

A Very Simple Implementation Of Insertion Sort : 

private void insertionSort(int[] intArray) {

    int temp = 0; // for holding current element.

  

    // start the iteration from second element i.e index = 1

    for(int i = 1; i < intArray.length; i++) {

  

    // we have to compare current element with its previous elements  

    for(int j = i; j > 0; j--) {

       temp = intArray[j];

       if(intArray[j] < intArray[j-1]) {

          // swap the elements

          intArray[j] = intArray[j-1];

          intArray[j-1] = temp;

       }

    }

}

An Improved Version Of Insertion Sort :

    In the above simple version of Insertion Sort, we have unnecessary iterations in inner for loop, this comes when all the preceding elements are less than current element. Insertion Sort, sorts lower part of the array/ list in each iteration, so you don't need to compare current element against all it's previous elements. So we can break the inner for loop, in case if any preceding element is less than current element. The improved code is below.

private void insertionSort(int[] intArray) {

    int temp = 0; // for holding current element.

  

    // start the iteration from second element i.e index = 1

    for(int i = 1; i < intArray.length; i++) {

  

    // we have to compare current element with its previous elements  

    for(int j = i; j > 0 && (intArray[j] < intArray[j-1]); j--) {

         temp = intArray[j];

          intArray[j] = intArray[j-1];

          intArray[j-1] = temp;       

    }

}

An illustration of Insertion Sort. Each column shows the array after
the iteration with the indicated value of i in the outer for loop. Values above
the line in each column have been sorted. Arrows indicate the upward motions of
records through the array.

Implementation Of Insertion Sort That Supports Any Object Array in Java :

private <A extends Comparable<A>> void insertionSort(A[] objArray) {

        A temp;

        for(int i = 1; i < objArray.length; i++) {



            // call compateTo() method to compare two objects.

            for(int j = i; (j > 0 ) && (objArray[j].compareTo(objArray[j-1]) < 0); j--) {

                temp = objArray[j];

                objArray[j] = objArray[j-1];

                objArray[j-1] = temp;

            }

        }

        

        for(A obj : objArray) {

            System.out.print(obj.toString() + " ");

        }

    }

When To Use Insertion Sort ?

    Even though Insertion Sort has O(n^2) as worst case time, Insertion Sort is the algorithm of choice either when the data is nearly sorted or when the problem size is small. Insertion Sort is often used as the recursive base case for higher overhead divide and conquer sorting algorithms, such as merge sort or quick sort, when the problem size is small.

Properties Of Insertion Sort : 

1. O(1) extra space in swapping.
2. O(n^2) comparisons & swappings.
3. Adaptive - O(n) time when nearly sorted.
4. Stable i.e doesn't change the relative order of elements with equal keys.

Measuring Time Complexity Of Insertion Sort : 

     The body of Insertion Sort is made up of two nested for loops. The Outer for loop is executed n-1 times. The inner for loop is harder to analyze because the number of times it executes depends on how many values are less than that of the key in position i.

In Worst Case :

    The worst case for Insertion Sort would occur if the keys are initially arranged from highest to lowest, in the reverse of sorted order. In this case the number of comparisons will be one for first time through the inner for loop, 2 for 2nd time & so on.

So , the total no of comparisons will be

1 + 2 + 3 + ----- + n = n(n+1) / 2 = n^2 / 2 = O(n^2).
  
In Best Case : 

    The best case occurs when the keys begin in sorted order from lowest to highest. In this case, every pass through the inner for loop will fail immediately and no values will be moved. The Total no of comparisons will be n-1, which is the no of times the outer for loop executes. Thus the best case of Insertion Sort is O(n).

In Average Case :

    Let's consider we have 10 elements in an array, Now we are at positon 6 (with respect to outer array). So we have to compare key at position 6 of the array with remaining keys that are in positions below 6. We expect on average that half of the keys that are lying in positions from 0 to 6 will have value greater than that of the key at position 6.
   
Thus the average case should be about half of the worst case i.e (n^2 / 2) /2 = n^2 / 4 = O(n^2).
   
There fore the average case is no better than the worst case in asymptotic complexity.