Insertion sort is next simple sorting algorithm after Bubble Sort. You may not have realized but you must have used insertion sort in a lot of places in your life. One of the best examples of insertion sort is,

Let's see one more example of insertion sort from real life. Have you noticed, how do tailors arrange shirts in wardrobe, according to size. So they insert new shirt at the proper position, for that, they shift existing shirts until they find the proper place.

If you consider wardrobe as array and shirts as an element, you will find out that we need to shift existing elements to find the right place for the new element. This is the

In this article, we will learn that by first understanding insertion sort with flowchart and by walking through an example. After that writing a Java method to do insertion sort will be very easy.

###

If you know how to sort a hand of cards, you know how insertion sort works; but for many programmers, it's not easy to translate real world knowledge into a working code example. This is where natural programming ability comes into play. A good programmer has the ability to code any algorithm, and convert a real life example to an algorithm.

Now, how do you sort an array of an integer using this algorithm? You can say that we can treat this array as a deck of card, and we will use another array to pick and place element from one place to another. Well, that will work, but it's a waste of space (memory), because what you are doing is comparing and shifting, which can also be done

Here is the

1) Consider the first element is sorted and it's on proper place, that is index 0 for your array.

2) Now go to the second element (index 1 in the array), and compare it with what is in your hand (the part of the array, which is already sorted). Which means you compare this element going backward towards index zero.

3) If the current number is smaller than the previous number (which is in the proper place), we need to put our current number before that. How will we do that? Well for that we need to shift existing number. But what if there is another element which is greater than our current element. It means we need to continue comparing until we found a proper place for our current number, which again means current number> existing number or we are at the start of the list (index 0 in the array).

4) We need to repeat this process for all the numbers in the list. Once we finish that, we have a sorted list or array.

In short, insertion sort is all about finding the proper place for current number. Once you find the proper place, you need to shift existing element to make a place for this new number. By the way, This algorithm can be better understood by looking at flowchart or a real example with numbers, as shown in the following diagram

##

It's said that

You can see that at last step our array is sorted in increasing order, starting from - 5 and ending at 16.

###

It's very easy to implement Insertion sort in Java. All you need to do is to iterate over the array and find proper position of each element, for that you need to shift element and you can do it by swapping. The logic of sorting integer array using insertion sort algorithm is inside method insertionSort(int[]). In Java you can also sort any object e.g. String using this algorithm, all you need to do is to use Comparable interface because that will provide you mechanism to compare two objects. Now instead of using > (greater than) or < (less than) operator, we need to use compareTo() method. For this we have decided to overload our insertionSort() method, where overloaded version takes an Object array instead of an int array. Both methods sort element using insertion sort logic. By the way, in the real world, you don't need to reinvent the wheel, java.util.Arrays class provides several utility method to operate upon arrays and one of them is sort. There are a couple of overloaded version of sort() method available to sort primitive and object arrays. This method uses double pivot QuickSort to sort the primitive array and MergeSort to sort object array. Anyway, here is our complete code example to run Insertion sort in Java. If you are using Eclipse IDE then just copy paste the code in src folder of your Java project and Eclipse will create packages and source file with the same name by itself. All you need to is that to run it as Java program.

That's all about

Algorithms and Data Structures - Part 1 and 2

Java Fundamentals, Part 1 and 2

Cracking the Coding Interview - 189 Questions and Solutions

*how you sort your hand in playing cards*. We pick one card from the deck, we assume it's sorted, and then we insert subsequent card in their proper position. For example, if our first card is Jack, and our next card Queen then we put that after Jack. Now if next card is King, we put it after the queen, and if we get 9, we put it before jack. So if you look closely, insertion sort is a perfect sorting algorithm to insert a new value into the already sorted list. That's why best-case complexity of insertion sort is O(n), in which case you insert a new number in the already sorted list of integers. Another thing to keep in mind is the size of the list, insertion sort is very good for small list or array, but not so for a large list, where QuickSort, MergeSort, and HeapSort rules.Let's see one more example of insertion sort from real life. Have you noticed, how do tailors arrange shirts in wardrobe, according to size. So they insert new shirt at the proper position, for that, they shift existing shirts until they find the proper place.

If you consider wardrobe as array and shirts as an element, you will find out that we need to shift existing elements to find the right place for the new element. This is the

*core of insertion sort algorithm*, if you understand these example, even you can come up with a step by step coding algorithm to sort an array of an integer using insertion sort in Java.In this article, we will learn that by first understanding insertion sort with flowchart and by walking through an example. After that writing a Java method to do insertion sort will be very easy.

###
__How Insertion Sort Algorithm works__

If you know how to sort a hand of cards, you know how insertion sort works; but for many programmers, it's not easy to translate real world knowledge into a working code example. This is where natural programming ability comes into play. A good programmer has the ability to code any algorithm, and convert a real life example to an algorithm.Now, how do you sort an array of an integer using this algorithm? You can say that we can treat this array as a deck of card, and we will use another array to pick and place element from one place to another. Well, that will work, but it's a waste of space (memory), because what you are doing is comparing and shifting, which can also be done

*in-place*in the same array.Here is the

**step by step guide to coding insertion sort algorithm in Java**:1) Consider the first element is sorted and it's on proper place, that is index 0 for your array.

2) Now go to the second element (index 1 in the array), and compare it with what is in your hand (the part of the array, which is already sorted). Which means you compare this element going backward towards index zero.

3) If the current number is smaller than the previous number (which is in the proper place), we need to put our current number before that. How will we do that? Well for that we need to shift existing number. But what if there is another element which is greater than our current element. It means we need to continue comparing until we found a proper place for our current number, which again means current number> existing number or we are at the start of the list (index 0 in the array).

4) We need to repeat this process for all the numbers in the list. Once we finish that, we have a sorted list or array.

In short, insertion sort is all about finding the proper place for current number. Once you find the proper place, you need to shift existing element to make a place for this new number. By the way, This algorithm can be better understood by looking at flowchart or a real example with numbers, as shown in the following diagram

##
__Pictorial explanation of Insertion Sort Algorithm__

It's said that *"A picture is worth thousand words",*this is quite true in the case of understanding sorting algorithm. Earlier we had seen how easy it was to understand QuickSort algorithm using a GIF image, and now we will again learn how Insertion sort works by following this diagram, It becomes extremely easy to explain how insertion sort works with this example. Here we have an integer array of both positive and negative numbers in random order. Our task is to sort this unsorted array using Insertion Sort in ascending order, which means smallest element should be at the start of the array and the largest element must be at the end of the array. To start working we assume that our first element is in the proper position (remember first card in your hand) and start with the second integer, which is -5. Now we compare it with 7, since - 5 is less than 7, we first move 7 in place of -5. After this we don't need to compare -5 with any other number because we have reached the left boundary, so we will put -5 at the current place. Now, we pick the third element which is 2. We compare 2 with 7 and found that 2 is also less than 7, which means 7 shifted in place of 2. Next, we compare 2 with -5, now 2 is greater than -5 so we insert it at this place. After this, we pick the fourth element which is 16. Since 16 is greater than 7, no need to shift anyone, 16 will remain in its place. Now last element 4, it is less than 16, so 16 will move in place of 4, next we compare 4 with 7, again 4 is less than so 7 will be shifted, after this we compare 4 with 2, wow it's greater that 2, so we have found a proper place for 4. We insert 4 there. Now there is no more element to process in array, so our array is now sorted.You can see that at last step our array is sorted in increasing order, starting from - 5 and ending at 16.

###
__Insertion Sort in Java with Example__

It's very easy to implement Insertion sort in Java. All you need to do is to iterate over the array and find proper position of each element, for that you need to shift element and you can do it by swapping. The logic of sorting integer array using insertion sort algorithm is inside method insertionSort(int[]). In Java you can also sort any object e.g. String using this algorithm, all you need to do is to use Comparable interface because that will provide you mechanism to compare two objects. Now instead of using > (greater than) or < (less than) operator, we need to use compareTo() method. For this we have decided to overload our insertionSort() method, where overloaded version takes an Object array instead of an int array. Both methods sort element using insertion sort logic. By the way, in the real world, you don't need to reinvent the wheel, java.util.Arrays class provides several utility method to operate upon arrays and one of them is sort. There are a couple of overloaded version of sort() method available to sort primitive and object arrays. This method uses double pivot QuickSort to sort the primitive array and MergeSort to sort object array. Anyway, here is our complete code example to run Insertion sort in Java. If you are using Eclipse IDE then just copy paste the code in src folder of your Java project and Eclipse will create packages and source file with the same name by itself. All you need to is that to run it as Java program.import java.util.Arrays; /** * Java program to sort an array using Insertion sort algorithm. * Insertion sort works great with already sorted, small arrays but not suitable for * large array with random order. * * @author Javin Paul */ public class InsertionSort { public static void main(String args[]) { // getting unsorted integer array for sorting int[] randomOrder = getRandomArray(9); System.out.println("Random Integer array before Sorting : " + Arrays.toString(randomOrder)); // sorting array using insertion sort in Java insertionSort(randomOrder); System.out.println("Sorted array uisng insretion sort : " + Arrays.toString(randomOrder)); // one more example of sorting array using insertion sort randomOrder = getRandomArray(7); System.out.println("Before Sorting : " + Arrays.toString(randomOrder)); insertionSort(randomOrder); System.out.println("After Sorting : " + Arrays.toString(randomOrder)); // Sorting String array using Insertion Sort in Java String[] cities = {"London", "Paris", "Tokyo", "NewYork", "Chicago"}; System.out.println("String array before sorting : " + Arrays.toString(cities)); insertionSort(cities); System.out.println("String array after sorting : " + Arrays.toString(cities)); } public static int[] getRandomArray(int length) { int[] numbers = new int[length]; for (int i = 0; i < length; i++) { numbers[i] = (int) (Math.random() * 100); } return numbers; } /* * Java implementation of insertion sort algorithm to sort * an integer array. */ public static void insertionSort(int[] array) { // insertion sort starts from second element for (int i = 1; i < array.length; i++) { int numberToInsert = array[i]; int compareIndex = i; while (compareIndex > 0 && array[compareIndex - 1] > numberToInsert) { array[compareIndex] = array[compareIndex - 1]; // shifting element compareIndex--; // moving backwards, towards index 0 } // compareIndex now denotes proper place for number to be sorted array[compareIndex] = numberToInsert; } } /* * Method to Sort String array using insertion sort in Java. * This can also sort any object array which implements * Comparable interface. */ public static void insertionSort(Comparable[] objArray) { // insertion sort starts from second element for (int i = 1; i < objArray.length; i++) { Comparable objectToSort = objArray[i]; int j = i; while (j > 0 && objArray[j - 1].compareTo(objectToSort) > 1) { objArray[j] = objArray[j - 1]; j--; } objArray[j] = objectToSort; } } } Output: Random Integer array before Sorting : [74, 87, 27, 6, 25, 94, 53, 91, 15] Sorted array uisng insretion sort : [6, 15, 25, 27, 53, 74, 87, 91, 94] Before Sorting : [71, 5, 60, 19, 4, 78, 42] After Sorting : [4, 5, 19, 42, 60, 71, 78] String array before sorting : [London, Paris, Tokyo, NewYork, Chicago] String array after sorting : [Chicago, London, NewYork, Paris, Tokyo]Another useful thing to learn from this example is how to generate Random numbers in Java. You can see that our getRandomArray(int length) method creates a random array of given length. This uses static utility method Math.random() which returns a double value between 0.0 to 0.1, if you need to convert it to an integer, in the range of 0 to 99, you need to multiply it with 100. After that, you can cast it to int to get rid of decimals.

That's all about

**Insertion sort in Java**. It's one of the really beautiful algorithms and works best for the already sorted list. It has lots of practical uses but has limitations also.*You should not use Insertion sort for sorting a big list of numbers*, as its best case performance is in order of O(n), which can be very high for a list of say 1 million integers. To short those list, you need sorting algorithms which have logarithmic complexity e.g. quicksort, mergesort or heapsort, which provides best case complexity of O(nLogn), because log reduces power of 10^n into n i.e. 1 million will become 10^6 means 6. In order to remember Insertion sort algorithm, just remember how you sort your hand in poker or any card game. If that is tough, just remember how you arrange your shirts in wardrobe.**Further Reading**Algorithms and Data Structures - Part 1 and 2

Java Fundamentals, Part 1 and 2

Cracking the Coding Interview - 189 Questions and Solutions

Insertion sort is next simple algorithm after infamous Bubble Sort. In my opinion this is the human's way of sorting things in order. You would have definitely used Insertions sort before without even realizing that you are using it, remember how do you arrange your hand in playing card came? Yes, that is Insertion sort. In this article, we will learn how to code Insertion sort in Java.

ReplyDeleteIn one of the interview, I was asked exactly this question "Given an array of N values, arrange them into ascending order using insertion sort", and guess what, I have coded "selection sort", came home happy without realizing that I have been doing it completely wrong, and only realized in night :).

ReplyDeleteBubble Sort, Insertion Sort and Selection sort are best left for academics. In today's heavy data age, they don't have any practical usage. Today we are looking for sorting algorithm which can sort millions of records in few micro seconds. On this point, Samsung has just release an algorihtm to sort tera bytes of data in few seconds.

ReplyDelete"Math.random() which returns a double value between 0.0 to 0.1"

ReplyDeleteshould be 0.0 to 1.0, because 0.0 <= Math.random() < 1.0

"objArray[j - 1].compareTo(objectToSort) > 1"

very likely should be " >0 ", because any positive value returned from compareTo is consider that o1 is greater than o2.