Today we will look into Insertion Sort in Java program. Insertion sort is similar to Bubble sort and in this post, we will go through the algorithm, example and then write a java code to sort the integer array using insertion sort algorithm.

## Insertion Sort in Java

In java insertion sort, we compare the value at any index from all the prior elements until all the lesser values are found. We place the value at the index before which there are no lesser values.

By doing this iteratively to the last index, we have a sorted array of integers.

Let’s understand it with an example.

Unsorted array: [5, 4, 14, 2, 8]

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]

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]

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]

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]

Key points to note when writing insertion sort 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 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]

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 small size of array 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.

Azad says

how we can use array instead of random numbers?

HJC says

Ah, finally.

Thanks, all the other websites instructs me to, at you line 31, to say ‘arr[j+1] = valueToSort;’ which will end up in me losing some values in the array, even, in some instances, change all the values in the array to the same value.

Thanks so very much!