Insertion Sort Implementation in Java

• Implement Insertion Sort Algorithm in Java
• Java Program Code for Insertion Sort
• Pros and Cons of Insertion Sort
• Analysis of Insertion Sort
• References

Implement Insertion Sort Algorithm in Java

Insertion sort executes in O(N²) time, but in some situation it outperforms bubble and selection sort. It is about twice as fast as the bubble sort and somewhat faster than the selection sort while sorting a nearly sorted array. Insertion sort becomes a good choice when we need to sort a almost sorted array. This is because most of the array items are already in place and there will be less number of shifts required. If the array is large and its entries are already in order (or nearly in order), then insertion sort is much, much faster than if the entries are randomly ordered or in reverse order.

Java Program Code for Insertion Sort

Developing Java code for insertion sort is also not too complex, although insertion sort slightly more involved than the bubble and selection sorts. To sort a given array of items we pick an item, shift the remaining items, and then insert the picked item in the correct place. This process is repeated until all the items are in the correct sequence. Following program develops a class InsertionSort containing a static generic method insertionSort. Note that Java provides the java.util.Comparable interface that contains a single method, compareTo. Any class that correctly implements this interface guarantees a total ordering of its instances.

/* Java Program code for insertion sort */
class InsertionSort 
{
  public static <T extends Comparable<T>> void insertionSort (T[] list, int size) 
  {
    int outCounter, inCounter;
    T temp;
    // Sort list[] into increasing order.
    for (outCounter = 1; outCounter < size; outCounter++)
    {
      temp = list[outCounter];
      for (inCounter = outCounter; inCounter > 0 && list[inCounter - 1].compareTo(temp) > 0; inCounter--)
      {
        list[inCounter] = list[inCounter - 1];
      }
      list[inCounter] = temp;
    }
  }
}
 
public class InsertionSortDemo
{
  public static void main (String[] args)
  {
    Integer arr[] = {10, 9, 8, 7, 6, 6, 4, 3, 2, 1};
    InsertionSort.insertionSort(arr, arr.length);
 
    System.out.println("Sorted Array: ");
    for(Integer i : arr)
    {
      System.out.println(i);
    }
  }
}
 
OUTPUT
======
Sorted Array:
1
2
3
4
6
6
7
8
9
10

In above implementation of insertionSort, we do not exchange list[inCounter] and list[inCounter - 1] in every iteration, rather we assign list[outCounter] to temp outside inner loop, and then use this temp in comparison, and finally when control gets out of inner loop we assign temp to list[inCounter]. It saves number of assignments done in every iteration.

Pros and Cons of Insertion Sort

Insertion sort is a good choice when the array to be sorted is almost sorted. This is because there will be less number of swaps. On the contrary, insertion is slow because all the elements after an element that is not in order have to be moved up, therefore not good for big arrays that are not partially sorted.

Analysis of Insertion Sort

In any case, the insertion sort runs in O(N²) time for random data. For data that is already sorted or almost sorted, the insertion sort does much better. When data is in order, the condition in the inner for loop is never true, so it becomes a simple statement in the outer loop, which executes N-1 times. In this case the algorithm runs in O(N) time. If the data is almost sorted, insertion sort runs in almost O(N) time.

However, for data arranged in inverse sorted order, every possible comparison and shift is carried out, so the insertion sort runs no faster than the bubble sort.

Last Word

In this tutorial we discussed insertion sort and developed Java program code for insertion sort. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

References