Java insertion sort

Java insertion sort
Insertion sort derives its name from the word insert where each time you pick an array element, it is inserted into its right position or index, according to the order, in which the array needs to be sorted.
This article will explain the logic of insertion sort followed by a java program based on this algorithm to sort an array of integers and string array.

Logic
Suppose you have an input array of integers as below.

 

 

 

This array needs to be sorted in ascending order of numbers. In Insertion sort, each array element is compared with all the elements before it and it is shifted to the left according to its comparison result with the elements before it.
Following is the sequence of operations that need to be performed in Insertion sort.

For each array element,
1. Compare it with the element before it.
2. If it is smaller, do nothing and move to the next element towards the left.
If the prior element is greater, then swap them so that the larger element moves towards right.

So, if we start with 1(third element) in the image below, it is compared with 23(element before 1).

 

 

 

 

3. Since the prior element is greater, interchange both.

 

 

 

 

After interchanging, compare the current element(1) again with the element before.

 

 

 

 

 

Since the current element is smaller than the element before, they are exchanged and the array becomes

 

 

 

 

If you see carefully, 1 comes to its correct position after it is compared with all the elements towards its left.

Similarly, these steps are repeated for all the elements of the array. This way, each element is inserted into its right position and this is how insertion sort works.

Algorithm
1. Loop over the elements of the array.
2. In every iteration, compare the current element with all the elements before it.
This would require another loop which is nested inside outer loop. This inner loop will execute from the outer loop index till 0(or start of array).
3. If the element before is greater than the current element, swap them. This step will be performed inside inner array.
After the inner loop completes, you will have a sorted sub-array, which lies before the outer loop current index.

After the outer loop completes, the array will be sorted in ascending order.
Implementation
Below is a java code to implement the pseudocode explained above.

public class InsertionSortExample {

  public static void main(String[] args) {
    int[] arr = { 12, 23, 1, 5, 9 };
    System.out.println("Before sorting: " + Arrays.toString(arr));
    // outer loop
    for (int i = 1; i < arr.length; i++) {
      // store current array element
      int current = arr[i];
      // index before the current element
      int j = i - 1;
      // loop from current element till start
      while (j >= 0 && arr[j] > current) {
        // swap if prior element is greater than current
        arr[j + 1] = arr[j];
        // move index towards left
        j--;
      }
      // place the current element into its position
      arr[j + 1] = current;
    }
    System.out.println("After sorting: " + Arrays.toString(arr));
  }
}

This prints

As you can see from the output, the array is sorted in ascending order.

Sorting string array
Insertion sort can also be used to sort an array of string values. The only difference is that string values can not be compared using logical operator(>).
We need to use compareTo() method for checking if one string is greater than other.
compareTo() is invoked on a string and it accepts another string as argument. It compares the strings alphabetically and returns an integer value as per the following conditions:

• Negative value or <0 , if the string on which it is called is lesser than the argument string.
  Example,  "ab".compareTo("cd");
• Positive value or >0 , if the string on which it is called is greater than the argument string.
  Example,  "xy".compareTo("cd");
• 0 , if both the strings are equal.
  Example,  "ab".compareTo("ab");

Java program to sort a string array based on insertion sort is given below.

public class InsertionSortExample {

  public static void main(String[] args) {
    String[] arr = { "owl", "cat", "apple", "ball", "east" };
    System.out.println("Before sorting: " + Arrays.toString(arr));
    // outer loop
    for (int i = 1; i < arr.length; i++) {
      // store current array element
      String current = arr[i];
      // index before the current element
      int j = i - 1;
      // loop from current element till start
      while (j >= 0 && arr[j].compareTo(current) > 0) {
        // swap if prior element is greater than current
        arr[j + 1] = arr[j];
        j--;
      }
      // place the current element into its position
      arr[j + 1] = current;
    }
    System.out.println("After sorting: " + Arrays.toString(arr));
  }
}

Output of this code is

String array is successfully sorted.
Time complexity
Following is the time complexity of insertion sort.
Best Case
Best case is when the array is already sorted in the order you wish. In this case, we need to iterate all the array elements[O(n)] but no swapping or shifting of elements is required[O(1)].
So, the time complexity is O(n).

Worst Case
Worst case is when the array is sorted in the reverse order than you wish. In this case, we need to iterate all the array elements[O(n)] and swap or shift elements[O(n)].
So, the time complexity is O(n²).

Average Case
Worst case is when the array is not sorted in any order and the elements are randomly distributed. In this case, we need to iterate all the array elements[O(n)] and swap or shift elements[O(n)].
So, the time complexity is O(n²).

Hope this article was useful.