Insertion Sort in Java – Algorithm and Code with example

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 Algorithm

In 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 this 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 algorithm based on above example and key points.

package com.vaibhav.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 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 sorting 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Current ye@r *

Subscribe to JournalDev Newsletter
Get the FREE access to Monthly Newsletter and Free PDF eBooks
*No Spam Guaranteed. By entering your email address, you agree also subscribing to our newsletter.
Oops! - Something went wrong.
Close
Today's Special: Web Application Development eBook Free Download Now
India's Independence Day Special: Java Persistence API eBook Free Download Now