Insertion Sort in java

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Sorting An Array Using Insertion Sort

Let us take an example of Insertion sort using an array.

The array to be sorted is as follows:

Now for each pass, we compare the current element to all its previous elements. So in the first pass, we start with the second element.

Thus, we require N number of passes to completely sort an array containing N number of elements.

The above illustration can be summarized in tabular form as shown below:

Pass	Unsorted list	comparison	Sorted list
1	{10,2,6,15,4,1}	{10,2}	{2,10, 6,15,4,1}
2	{2,10, 6,15,4,1}	{2,10, 6}	{2,6, 10,15,4,1}
3	{2,6, 10,15,4,1}	{2,6, 10,15}	{2,6, 10,15,4,1}
4	{2,6, 10,15,4,1}	{2,6, 10,15,4}	{2,4,6, 10,15,1}
5	{2,4,6, 10,15,1}	{2,4,6, 10,15,1}	{1,2,4,6, 10,15}
6	{}	{}	{1,2,4,6, 10,15}

As shown in the illustration above, at the end of each pass, one element goes in its proper place. Hence in general, to place N elements in their proper place, we need N-1 passes.

Now let's see some program of insertion sort:

 package com.ritesh;

 import java.util.Arrays;

 public class InsertionSort {
    public static void main(String[] args) {
        int[] numArray = {10,6,15,4,1,45};
        System.out.println("Original Array:" + Arrays.toString(numArray));
        //apply insertion sort algorithm on the array
        for(int k=1; k<numArray.length-1; k++)   {
            int temp = numArray[k];
            int j= k-1;
            while(j>=0 && temp <= numArray[j])   {
                numArray[j+1] = numArray[j];
                j = j-1;
            }
            numArray[j+1] = temp;
        }
        //print the sorted array
        System.out.println("Sorted Array:" + Arrays.toString(numArray));
    }
 }