Insertion Sort in Java

June 18, 2022

Insertion Sort in Java

This is an in-place comparison-based sorting algorithm, which is idle for small data-sets. Insertion sort is almost a resemblance of the way we sort playing cards in our hand. In this algorithm, we try to insert the elements of the array into an already sorted array.

Insertion Sort Java
Time Complexity O(n2)
Best Case Ω(n)
Worst Case O(n2)
Aux. Space Complexity O(1)
Best case when Array is already sorted
Worst case when Array is reverse sorted

Working of Insertion Sort

  • Consider that there are 5 elements in an array which are to be sorted.
  • First, we consider the 0th index as sorted part and the rest is unsorted.
  • Then we compare the next element of the array with the first element of the array, if the first element is smaller then the second element then we swap the elements, otherwise we place the element after the first element
  • Thus each time we insert element the sorted array becomes larger and unsorted becomes smaller, and the new element is to be compare with all the previous elements of the sorted array and adjust the element just next to its smaller element.
  • We repeat this process till all the elements in array become part of the sorted array
Insertion sort in Java
Insertion Sort in Java Example

Code for Insertion Sort in JAVA

Run 
// Java Program for Insertion Sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best Case : When already Sorted, Worst Case : When reverse Sorted
class Main
{
    // Main method
    public static void main(String args[])
    {
        int a[] = {11, 9, 7, 15, 6, 10, 5, 17};

        System.out.println("Array Before Insertion Sort: ");
        printArray(a);

        insertionSort(a);

        System.out.println("Array After Insertion Sort: ");
        printArray(a);
    }

    /*Function to sort array using insertion sort*/
    static void insertionSort(int arr[])
    {
        int len = arr.length; //calculating the length of the array
        for (int i = 1; i < len; i++) 
        { 
            int key = arr[i]; 
            int j = i - 1; 

            /* Shift elements of a[i-1 .... 0], that are greater 
            than key, to one position right of their 
            current position */ 
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    /* A utility function to print array of size n*/
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i = 0; i < len; ++i)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}

Output

5 6 11 12 13

Plus Points

  • Easy to understand and write
  • Works efficiently on smaller data sets in number
  • Uses no additional memory for sorting as is in place algorithm with O(1) space complexity
  • If data sets are already sorted or nearly sorted then has O(n) space complexity

Negative Points

  • Very bad average time complexity of O(n2)
  • Shifting items because of insertion can be costly
Insertion Sort in Java meme

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting