Insertion Sort Program in Java

In this post we’ll see how to write Insertion sort program in Java. Insertion sort is good for sorting a small set of elements. Out of the three simpler sorting algorithms insertion sort, selection sort and bubble sort, insertion sort is considered a better option in most of the scenarios.

How Insertion sort works

In insertion sort you take one element at a time and the elements on the left side of the current element are considered temporarily sorted for example if you are at 4th index then elements at index 1..3 are sorted among themselves. But that is not yet the final position because any other element may have to be inserted in between these temporarily sorted elements, which means elements have to be shifted right to make place for the insertion of the element that is why the name insertion sort.

In each iteration the elements on the left of the current element are sorted and current element is compared with all the elements on its left, if it is smaller than any of these elements then it has to be inserted at that index and the elements have to be shifted right to make place for it.

For example if you have an array [5, 2, 6, 1] then you will start with 2 (2nd element) and compare it with elements on its left.

In first iteration 2 is compared with 5. Since it is smaller so it has to be inserted in the place of 5 and other elements have to shifted right. Which gives the array as [2, 5, 6, 1] after first iteration.
In second iteration 6 is compared with 5, since 6 is greater than 5 so nothing needs to be done. So array is still [2, 5, 6, 1].
In third iteration 1 is compared with 6, since it is smaller so elements have to be shifted right which makes the array as [2, 5, 6, 6]. Note that there are more elements on the left to be compared so 1 is still not inserted as its final insertion point is still not sure at this point.
Then 1 is compared with 5, since 1 is smaller so elements have to be shifted right which makes the array as [2, 5, 5, 6].
Then 1 is compared with 2, since 1 is smaller so elements have to be shifted right which makes the array as [2, 2, 5, 6].
At this point left most index is reached so we know that 1 is the smallest element so it is inserted at this index making the array as [1, 2, 5, 6].

Insertion Sort Java program

Logic for writing the insertion sort Java program is as follows-

You take one element (starting from the second element) at a time starting from left to right in the outer loop. Also assign this element to a temporary variable.

In inner loop, which starts at the same number as the outer loop and moves toward left, you compare the temp variable with all the previous elements (element on the left of the current index element).

This comparison goes on till both of these conditions hold true-

Elements on the left side are greater than the element at the current index.
Leftmost element is reached.

In each iteration with in this inner loop you also have to shift right by assigning the previous element to the element at the current index with in the inner loop.

public class InsertionSort {
  public static void main(String[] args) {
    int[] intArr = {47, 85, 62, 34, 7, 10, 92, 106, 2, 54};
    int[] sortedArray = insertionSort(intArr);
    System.out.println("Sorted array is- ");
    for(int num : sortedArray){
      System.out.print(num + " ");
    }
  }
    
  private static int[] insertionSort(int[] intArr){
    int temp;
    int j;
    for(int i = 1; i < intArr.length; i++){
      temp = intArr[i];
      j = i;
      while(j > 0 && intArr[j - 1] > temp){
        // shifting elements to right
        intArr[j] = intArr[j - 1];
        --j;
      }
      // insertion of the element
      intArr[j] = temp;
    }
    return intArr;
  }
}

Output

Sorted array is- 
2 7 10 34 47 54 62 85 92 106

Time and space complexity of Insertion sort

If you have noticed in the program each time, the number of elements that are to be compared, increases in progression; in first iteration only one element has to be compared, in second iteration two elements have to be compared and so on. Which gives us the number of comparison as–

1 + 2 + 3 + ............ + N-1 = N*(N-1)/2

Which makes the Insertion sort time complexity as O(N²).

In the best case scenario, if the array is already sorted or almost sorted the while loop condition will return false making the time complexity as O(N) if it is already sorted or almost O(N) if the data is almost sorted.

Insertion sort is an in place sorting algorithm so apart from the initial array there is no auxiliary space requirement, thus the space complexity of Insertion sort is O(1), total space can be considered as O(N).

That's all for this topic Insertion Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Tuesday, January 11, 2022