Insertion Sort in Java With Examples [Latest]

Insertion Sort in Java

1. In java insertion sort, we compare the value at any index from all the prior elements until all the lesser values are found.
2. Then we place the value at the index before which there are no lesser values.
3. Above two steps are done iteratively to the last index, finally we have a sorted array of integers.

Insertion Sort Algorithm Example

Let’s understand insertion sort algorithm with an example. Let’s say we have an unsorted array [5, 4, 14, 2, 8].

1. 1st index iteration: value at 1st index = 4, which is less than 5, so array becomes [5, 5, 14, 2, 8], as we reached the start we place the value at 0th index and array becomes [4, 5, 14, 2, 8]
2. 2nd index iteration: value at 2nd index = 14 which is greater than 5, so leave the array as it is. Now array = [4, 5, 14, 2, 8]
3. 3rd index iteration: value at 3rd index = 2 which is smaller than 14, so array becomes [4, 5, 14, 14, 8], again 2 is smaller than 5, so array becomes [4, 5, 5, 14, 8]. Again 2 is smaller than 4, so array becomes [4, 4, 5, 14, 8]. As we reached the start of array, we place 2 at 0th index and array becomes [2, 4, 5, 14, 8]
4. 4th index iteration: value at 4th index = 8, so array becomes [2, 4, 5, 14, 14], then 8 is greater than 5, so place 8 at the 14th place and array becomes [2, 4, 5, 8, 14]. And our array is sorted now.

Java Insertion Sort

Key points to remember when writing insertion sort implementation in java program:

• Start with 2nd element to the last element of the array, so use a for loop.
• Store the value into another variable to avoid it being lost when we change the index value in between.
• We need to keep changing the values until we are at 0th index or we found prior value to be greater, so we can use a while loop for this.

Here is the implementation of the insertion sort in java based on the above example and key points.

package com.journaldev.test;
import java.util.Arrays;
public class InsertionSort {
	public static void main(String[] args) {
		int A[] = new int[10];
		populateArray(A);
		System.out.println("Before Sorting: ");
		printArray(A);
		// sort the array
		insertionSort(A);
		System.out.println("nAfter Sorting: ");
		printArray(A);
	}
	/**
	 * This method will sort the integer array using insertion sort in java algorithm
	 *
	 * @param arr
	 */
	private static void insertionSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int valueToSort = arr[i];
			int j = i;
			while (j > 0 && arr[j - 1] > valueToSort) {
				arr[j] = arr[j - 1];
				j--;
			}
			arr[j] = valueToSort;
		}
	}
	public static void printArray(int[] B) {
		System.out.println(Arrays.toString(B));
	}
	public static void populateArray(int[] B) {
		for (int i = 0; i < B.length; i++) {
			B[i] = (int) (Math.random() * 100);
		}
	}
}

I am using random number generator code and the output for me for above program is:

Before Sorting:
[57, 90, 80, 48, 35, 91, 1, 83, 32, 53]
After Sorting:
[1, 32, 35, 48, 53, 57, 80, 83, 90, 91]

Insertion Sort Complexity

The complexity of insertion sorting is O(n) for best case (already sorted array) and O(n2) for worst case (sorted in reverse order).

Insertion sort in Java is a good choice for the array of small sizes and when you know that values will be mostly sorted. For example, sorting an array of size 100 where you know that all the values will be in between 1 to 10. That’s all for insertion sort in java.

Reference: Wikipedia