Insertion Sort in Java

July 26, 2020

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.

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

Code for Insertion Sort in JAVA

// Java Code for implementation of Insertion Sort 
class PrepInsta
	{ 
		// Main method 
   public static void main(String args[]) 
    { 
        int a[] = { 12,11,13,5,6 };

        PrepInsta ob = new PrepInsta(); 
        ob.sort(a); 

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

            /* Shift elements of a[0..i-1], that are 
               greater than key, to one position ahead 
               of their current position */
            while (j >= 0 && a[j] > key) 
				{ 
                  a[j + 1] = a[j]; 
                  j = j - 1; 
                } 
                   a[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(); 
    } 
  }

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(n²)
Shifting items because of insertion can be costly