Insertion Sort

June 24, 2019

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.

  • 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
Insertion Sort (3)

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(); 
    } 
  }
Capture1

Time Complexity of Insertion Sort 

Running time is an important aspect to consider when selecting a sorting algorithm since efficiency is often thought of in terms of speed. Insertion sort has an average and worst-case running time of O(n^2), so in most cases, a faster algorithm is more desirable.

Please Login/Signup to comment

One comment on “Insertion Sort”