Insertion sort program in java

Insertion sort

 
The Insertion sort algorithm views the data in two halves.
 
The left half of sorted elements and the right half of elements to be sorted.
 
In each iteration, one element from the right half is taken and added to the left half so that the left half is still sorted.
 
 
Insertion sort is of order O(n2)
 
Here is the implementation of Insertion order logic for sorting an array of integers.
 

  private void insertionSort(int[] elements) {
    for (int i = 1; i < elements.length; i++) {
      int key = elements[i];
      int j = i - 1;
      while (j >= 0 && key < elements[j]) {
        elements[j + 1] = elements[j];
        j--;
      }// end while loop
      elements[j + 1] = key;
    }// end for loop
  }

 
Input:
 
int[] elements = { 3, 2, 5, 7, 1,9};
 
Output
 
1,2,3,5,7,9
 
 
What if we want to sort an array of Strings instead ?
 

We can change the element comparison logic in the while loop to use compareTo() method to have a more generic implementation. This can accept any array of elements implementing Comparable interface.
 

Here is the code for sorting a String array :
 

  private static void insertionSort(String[] elements) {
    for (int i = 1; i < elements.length; i++) {
      String key = elements[i];
      int j = i - 1;
      while (j >= 0 && (key.compareTo(elements[j]) < 0)) {
        elements[j + 1] = elements[j];
        j--;
      }// end while loop
      elements[j + 1] = key;
    }// end for loop
  }

 

Input:
 
String[] elements = { “Http”,”Top”, “Java”, “Tutorial”,”Dot”, “Com”};
 
Output:
 
Com,Dot,Http,Java,Top,Tutorial

 
 
Do you have a better implementation ? Please share in the comments section.
 
 

© 2016, https:. All rights reserved. On republishing this post, you must provide link to original post

One comment

  1. […] Insertion Sort program in Java […]

Leave a Reply.. code can be added in <code> </code> tags

%d bloggers like this: