HowToDoInJava

  • Java 8
  • Regex
  • Concurrency
  • Best Practices
  • Spring Boot
  • JUnit5
  • Interview Questions
  • Dark Mode

Insertion Sort Java Example

By Lokesh Gupta | Filed Under: Algorithms

Insertion Sort is a simple and slow sorting algorithm that repeatedly takes the next element from the un-sorted section and inserts it into the sorted section at the correct position.

The idea of insertion sort comes from our daily life experiences. For example, when you play cards with your friends, you will insert the next card you pick into the sorted cards in your hand.

Insertion sort algorithm

The basic idea of insertion sort algorithm can be described as these steps:

  1. Data elements are grouped into two sections: a sorted section and an un-sorted section.
  2. Take an element from the un-sorted section.
  3. Insert the element into the sorted section at the correct position based on the comparable property.
  4. Repeat step 2 and 3 until no more elements left in the un-sorted section.

Insertion sort advantages

Though insertion sort is clearly slower than other sorting algorithms such as Merge Sort, but it has some good advantages in particular cases:

  • Efficient for small data input sets
  • It is adaptive i.e. efficient for data sets that are already substantially sorted
  • It is stable; i.e. does not change the relative order of elements with equal keys
  • It is online; i.e. can sort a list as it receives it

Insertion Sort Java Implementation

public class InsertionSortExample 
{
	public static void main(String[] args) 
	{
		//This is unsorted array
		Integer[] array = new Integer[] {12,13,24,10,3,6,90,70};
		
		//Let's sort using insertion sort
		insertionSort(array, 0, array.length);
		
		//Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void insertionSort(Object[] a, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = fromIndex + 1; i < toIndex; i++) 
		{
			d = a[i];
			int j = i;
			while (j > fromIndex && ((Comparable) a[j - 1]).compareTo(d) > 0) 
			{
				a[j] = a[j - 1];
				j--;
			}
			a[j] = d;
		}
	}
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

Insertion Sort Performance Improvement

If you look at previous implementation then you can easily identify that iterating over array to find correct spot inside already sorted array seems most time taking task and which can easily be improved using more fast search algorithm.

As we see that array is sorted already, so we can employ binary search algorithm which is more effective for already sorted arrays. So our improved insertion sort algorithm will become:

public class InsertionSortExample 
{
	public static void main(String[] args) 
	{
		// This is unsorted array
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };

		// Let's sort using insertion sort
		insertionSortImproved(array, 0, array.length);

		// Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void insertionSortImproved(Object[] a, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = fromIndex + 1; i < toIndex; i++)
		{
			d = a[i];
			int jLeft = fromIndex;
			int jRight = i - 1;
			//Check if its current position is it's suitable position
			if (((Comparable) a[jRight]).compareTo(d) > 0) 
			{
				//Perform binary search
				while (jRight - jLeft >= 2) 
				{
					int jMiddle = (jRight - jLeft) / 2 + jLeft - 1;
					if (((Comparable) a[jMiddle]).compareTo(d) > 0) {
						jRight = jMiddle;
					} else {
						jLeft = jMiddle + 1;
					}
				}
				if (jRight - jLeft == 1) 
				{
					int jMiddle = jLeft;
					if (((Comparable) a[jMiddle]).compareTo(d) > 0) {
						jRight = jMiddle;
					} else {
						jLeft = jMiddle + 1;
					}
				}
				//Place the element
				int j = i;
				for (j = i; j > jLeft; j--) 
				{
					a[j] = a[j - 1];
				}
				a[j] = d;
			}
		}
	}
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

Of course, it has more lines of code, but it will definitely improve performance of overall sorting time.

Happy Learning !!

Ref: https://en.wikipedia.org/wiki/Insertion_sort

TwitterFacebookLinkedinRedditPocket

About Lokesh Gupta

A family guy with fun loving nature. Love computers, programming and solving everyday problems. Find me on Facebook and Twitter.

1
Leave a Reply

This comment form is under antispam protection
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
This comment form is under antispam protection
  Subscribe  
newest oldest most voted
Notify of
Val

You will decrease performance with such improvements if compareTo method is simple (contains only several actions with primitives)

Vote Up0Vote Down  Reply
4 years ago

Search Tutorials

Java Algorithms

  • Algorithm – Introduction
  • Algorithm – Bubble Sort
  • Algorithm – Insertion Sort
  • Algorithm – Merge Sort
  • Algorithm – Quick Sort
  • Algorithm – Selection Sort
  • Algorithm – AES
  • Algorithm – Soundex
  • Algorithm – Compare and Swap

Popular Tutorials

  • Java 8 Tutorial
  • Core Java Tutorial
  • Collections in Java
  • Java Concurrency
  • Spring Boot Tutorial
  • Spring AOP Tutorial
  • Spring MVC Tutorial
  • Spring Security Tutorial
  • Hibernate Tutorial
  • Python Tutorial
  • Jersey Tutorial
  • Maven Tutorial
  • Log4j Tutorial
  • Regex Tutorial

Meta Links

  • Advertise
  • Contact Us
  • Privacy policy
  • About Me

Recommended Reading

  • 10 Life Lessons
  • Secure Hash Algorithms
  • How Web Servers work?
  • How Java I/O Works Internally?
  • Best Way to Learn Java
  • Java Best Practices Guide
  • Microservices Tutorial
  • REST API Tutorial
  • How to Start New Blog

Copyright © 2016 · HowToDoInjava.com · All Rights Reserved. | Sitemap

wpDiscuz