Insertion Sort in Java

Filed Under: Java

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

Insertion Sort in Java

insertion sort java code, 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

Comments

  1. Daniel says:

    Í love you, i’ve been at this problem for 3 days, thank you so much

  2. robert chase says:

    thank you…..

  3. robert chase says:

    realy helpful……….thanks

  4. tif says:

    how can I adapt this to accepting comma separated arguments (number) and sorting them. That is where i am getting confused.

  5. Azad says:

    how we can use array instead of random numbers?

  6. 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!

Leave a Reply

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

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages