Insertion Sort Algorithm in Java to Sort Array

Insertion sort is another simple sorting algorithm, which can be used to sort any linear data structure like array and linked list. On simplicity this is next to bubble sort, and it’s also pretty close to how humans manually sort something (for example, a hand of playing cards). As name suggest, Insertion sort is based upon insertion of element in a sorted list. To start, we assume that first element is already sorted. Then we pick next element and put it on second place, we compare this number with first element and if they are not in sorted order, we swap them. This gives a new sorted list of 2 elements. Now we pick third element and put it on 3rd place and compare it with 2nd placed number, if they are not in sorted order, we swap them, if all three elements are still not in sorted order then we again swap 1st and 2nd element, now we have a sorted list of three numbers. So in best case, we just need one comparison and no swapping, while In worst case we need to compare new number with each number in the sorted list i.e. k comparison, and k -1 swapping, where k is the length of sorted list.





I think Insertion sort is pretty easy to understand, isn't it; if you still don't get remember how you arrange your hand of cards, first you pick one card, then pick next card and put it after first card if it is bigger or before first card if it is smaller; then you pick another card and insert it to its proper position.  One more real world example of insertion sort is how tailors arrange shirts in cupboard, they always keep sort in sorted order of size and insert new shirt at right position. By the way if you notice trend then you can see that as length of our sorted list increased, so as number of comparison and swapping, which means this this sorting algorithm is not suitable for large data set. Indeed, it’s not as good as quicksort, heap sort or merge sort for sorting large arrays, but it’s good enough to sort small integer arrays where cost of comparison is small. By the way this algorithm is not just bound to numbers or integers, you can also sort String array with insertion sort or any list of Employee, depending they implement Comparator or Comparable to provide comparison logic. Insertion sort can also be used to sort any List of elements in Java. We will see more advantages and disadvantage of insertion sort in last section for now let's see pseudo code for insertion sort.

Pseudo Code for Insertion sort

As I said on insertion sort we assume first element is already sorted, what this mean to us is that we don't need to start at first element, so loop starts from 2nd element. Since array index are zero based in Java, our pseudo code starts with i=1 (2nd index). Here is n is total number of element i.e. length of array.

// outer loop for going through each element

for i=1 to n-1 {

   j = i ;

   // insertion and comparison

    while(j> 0) and A[j] < A[j-1]{

        swap(A[j], A[j-1]);

        j = j -1;

    }

}

You can see that we go through each element and compare whether it is in proper position or not. Swapping only occurs if element is not at its right position. This would be very clear by looking at insertion sort in action using a GIF images. To be frank, animation has helped me a lot to understand how a particular algorithm works. Your mind like to see things moving and if you have a good animation or video tutorial for any algorithm, use that. One more thing which helped me a lot is creating flow charts. Once you understand the algorithm, try creating a flowchart of logic by your own, this will ensure that your mind use the knowledge you just learned, a signal that this is a useful stuff. This eventually helps to retain knowledge for long time.

Insertion Sort in Action

Here is an illustration or example of how insertion sort algorithm works. In this image, we have an unsorted array of integers. First element in the array is 6, we assume it is sorted and on its proper position. Now next element is 5, if we have to sort the array on increasing order, we will compare 5 with 6, since 5 is less than 6, it will shift and 5 will take place of 6. Now next element is 3, we again compare 6 with 3, since 3 is less than 6, 6 will shift in place of 3; then again 3 will be compared to 5, again 5 will shift and 3 will take place of 5. This comparison and shifting will take place until we reach at the end of array. At this time your array is sorted.

Since a picture is worth a thousand word, just follow below animation and you will learn what I am saying. If you miss the start, just refresh the page and animation will start again from first element.

Insertion Sort implementation in Java

In this Java program, we will sort an integer array using Insertion sort algorithm in Java. As I said, insertion sort should only be used with small arrays or linked list, we are going to use an integer array of length 7, which contains numbers in random order. We have a method called insertionSort(int[] input) which takes an unsorted array and sorts it. If you look at the logic, you will first see that we are looping over integer array, starting from second element. On inner loop we initialize the index with next element e.g. in first iteration, j=1 and it will point to second element. Inner loop is used to compare current element with already sorted element, that's why after each iteration we decrease j by 1, here j>0 condition stops when we reach at the beginning of array. Shifting and swapping of element occur only if current element is less than already sorted element. Like in our code example, 32 is first element so it is sorted, next is 23 so we compare it to 32, now 23 is less than 32 so we will swap 32 and 23 position. I have inline swapping logic but you can also create a method swap just to make algorithm more readable. If you don't understand how swapping of integer works, then see this article. Once we came out of the outer loop, our int array is sorted on ascending order.

import java.util.Arrays;
/**
 * Java program to implement insertion sort in Java. In this example, we will
 * sort an integer array using insertion sort algorithm. This logic can be used
 * to sort array of String, or any other object which implements Comparable or
 * Comparator interface in Java.
 *
 * @author Javin Paul
 */
public class InsertionSortDemo {

    public static void main(String args[]) {
        // unsorted integer array
        int[] unsorted = {32, 23, 45, 87, 92, 31, 19};
        System.out.println("integer array before sorting : " + Arrays.toString(unsorted));
        insertionSort(unsorted);
        System.out.println("integer array after sorting  : " + Arrays.toString(unsorted));
    }


    /*
     * Sort integer array using Insertion sort algorithm.
     * only good for small array.
     */
    public static void insertionSort(int[] unsorted) {
        for (int i = 1; i < unsorted.length; i++) {
            int j = i;
            while (j > 0 && unsorted[j] < unsorted[j - 1]) {
                //swap
                int temp = unsorted[j - 1];
                unsorted[j - 1] = unsorted[j];
                unsorted[j] = temp;
                j--;
            }
        }
    }

}

Output:
integer array before sorting : [32, 23, 45, 87, 92, 31, 19]
integer array after sorting : [19, 23, 31, 32, 45, 87, 92]

Complexity Analysis

Once you know how an algorithm works, next task is to figure out its time and space complexity. If you have asked to write insertion sort algorithm on interview, rest assured that interviewer will ask you to calculate best case, average case and worst case time complexity. If you have understood algorithm correctly then it shouldn't be difficult. Look, what would be best case for sorting, an already sorted array right? So suppose we get an already sorted array, how will insertion sort work there? it assume first element is sorted, so it will pick next element and compare it with first element, since it's sorted list this will be greater than first element and no swapping will occur. In the end only n - 2 comparison will be required and no swapping. This means an O(n) time complexity in best case. Now, what would be the worst case for sorting an array, an already sorted list but in reverse order. Again,first iteration will start with second number, to sort this we need 1 comparison and 1 swapping, for 2nd iteration and to sort 3rd element we will be needing 2 comparison and 2 shifting. So for n-1 iteration, you will need n comparison and n shift. which means O(n^2) time complexity. The average case is in between best and worst case, which is again in order of  O(n ^2). This is the main reason why insertion sort is not suitable for sorting large array, because to sort 100 numbers, you will be needing time in order of 100*100. 

Advantages and Disadvantages of Insertion Sort Algorithm

Insertion sort has advantage of already sorted list over Bubble Sort algorithm. It requires fewer comparison then bubble sort, unless the list is backward. If array is already sorted then we only make n comparison, i.e. one comparison per element. With a sorted array, which just need to keep inserting elements. Insertion sort has following advantages compared to other similar sorting algorithms



1) Simple implementation, Insertion sort is next to bubble sort in simplicity. In classes and training it is taught along with selection sort and quick sort.



2) Insertion sort is efficient for small arrays but not suitable for large data sets.



3) Insertion sort is additionally efficient for lists that are already substantially sorted. In those cases time complexity is O(n + d), where d is the number of inversions.



4) Insertion sort is more efficient in practice than most other quadratic or O(n^2) algorithms such as selection sort and  bubble sort; the best case complexity for nearly sorted array is O(n).



5) Insertion sort is stable sorting algorithm i.e. it does not change the relative order of elements with equal keys



6) Insertion sort does In-place sorting ; i.e., only requires a constant amount O(1) of additional memory space





That's all about Insertion sort in Java. It's one of the fundamental sorting algorithm, and as a Java developer you should know how to write code to sort an integer array using insertion sort. This is quite often asked in Java interviews and written test. By the way, don't use insertion sort in production code, instead use Collections.sort() method, which is based on merge sort. Alternatively you can also use quicksort for sorting any array or List in Java.

Source:http://javarevisited.blogspot.com/2014/12/insertion-sort-algorithm-in-java-to-array-example.html