Insertion Sort in Java

Insertion Sort is also one of the few simplest and easy sorting available like Bubble Sort.
The technique used here is the technique we use while playing cards. The way we pick cards from deck and arrange each card inserting each one in its position while we hold the cards in hand. That's how the name is derived from - "insertion".




Let us see the explanation of this sorting with the below gif.
Taking one element at a time we will place the elements in its position comparing each element till we find its perfect position.
Just Like Bubble sort, Insertion sort also uses two loops. First loop picks elements one by one, in second loop the element picked is compared and placed in its suitable position.


Let get hands on by writing a Java code for it.

import java.util.Arrays;

class InsertionSort
{
    void sort(int arr[])
    {
        for (int i=1; i < arr.length; ++i)
        {
            int key = arr[i];
            int j = i-1;
            while (j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }
 
    public static void main(String args[])
    {        
        int arr[] = {12, 11, 13, 5, 6};
 
        InsertionSort is = new InsertionSort();  
        System.out.println("Array before sort " + Arrays.toString(arr));
        is.sort(arr);
        System.out.println("Array after sort " + Arrays.toString(arr));
    }
}
//output
//Array before sort [12, 11, 13, 5, 6]
//Array after sort [5, 6, 11, 12, 13]

Analysis of Insertion Sort

• Time Complexity: O(n*n)
• Auxiliary Space: O(1)
• Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
• Algorithmic Paradigm: Incremental Approach
• Sorting In Place: Yes
• Stable: Yes

Uses: Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Hope you like it. Stay tune for discussion for other sorting algorithms. Please comment for any doubts.

Happy Learning !!!

SHARE

Onlinecodegeek