Sunday 21 February 2016

Insertion sort in Java


Dear Friends I am with you with implementation of Insertion sort in Java.

It is an easy sorting algorithm. Please find below the code in java for the same. The code contains necessary comments to understand the steps.



import java.util.Arrays;
/**
 * 
 * @author krishna.k
 *
 */
public class InsersionSort {
    public static void main(String[] args) {
        int arr[] = {1,2,5,4,3,6,5,4,8,7,9,0,1,2,4,3,4,43,43,41,40,35,38,4,57,3,5,7,3,66,454,745,556465,3455,217,0,8769,-99,657,545,343,32433,46,546,9,-90,0,2,7,-10,-1};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * Best case : all the elements are already sorted : see in this case the second loop [ inner loop ] will break so O(n)
     * Worst case : elements are sorted in reverse order. both the loops will work till their bounds so O(n2)
     * Average case : O(n2).
     * 
     * This is best sorting when array size is very small. Although for small sized arrays it seams average case running time of O(n2) 
     * but due to less steps and less computations this is better than other sorts with n*log(n) running time.
     * 
     */
    public static void insertionSort(int[] arr) {
        if (arr != null) {
            int size = arr.length;
            // first loop iterates the array from 2nd element (at index 1) till the end. 
            // element at i-th [candidate element] is the element for which position needs to be decided.
            for (int i = 1; i < size; i++) { 
                int candidateElement = arr[i]; // storing the candidate element
                int j = i-1;
                for (; j >= 0 && arr[j] > candidateElement; j--) { // Second array scans and compares the candidate elements with the elements before it in the array
                    arr[j+1] = arr[j];// in case candidate element is smaller then current element at jth position needs to shift forward, so storing it at j+1th position. 
                }
                // in case shifting of elements were done as per the value of candidate element then due to decrementing the j after each shifting, need to do +1 in j to 
                // put the candidate element at its correct position.
                
                // in case no shifting was done and as j was initialized with i-1 hence +1 needs to be done for j
                //so as candidate element is put at its current position as it is. 
                arr[j+1] = candidateElement;// Inserting the current element in its correct position.
            }
        }
    }
}



Please go through the code above and then see below steps [sort of dry run] for better understanding.
Outer loop 1st iteration:


index
0
1
2
3
4
5
arr
1
2
5
3
8
6

i = 1
j = i-1 = 0
candidateElement = arr[i] = arr[1] = 2
arr[j] > candidateElement => arr[0] > 2 == 1 > 2 => false so break second loop
arr[j+1] = candidateElement => arr[0+1] = 2 => 2 remains at same position


Outer loop 2nd Iteration:


index
0
1
2
3
4
5
arr
1
2
5
3
8
6
 
i = 2
j = i-1 = 1
candidateElement = arr[i] =arr[2] =  5
arr[j] > candidateElement => arr[1] > 5 => 2 > 5 => false so break second loop
arr[j+1] = candidateElement => arr[1+1] = 5 => 5 remains at same position 


Outer loop 3rd Iteration:


index
0
1
2
3
4
5
arr
1
2
5
3
8
6

i = 3
j = i-1 = 2
candidateElement = arr[i] =arr[3] =  3
arr[j] > candidateElement => arr[2] > 3 => 5 > 3 => true
arr[j+1] = arr[j]  => arr[2+1] = arr[2] => arr[3] = arr[2]


index
0
1
2
3
4
5
arr
1
2
5
5
8
6

j-- = j-1 = 2-1 = 1
arr[j] > candidateElement => arr[1] > 3 => 2 > 3 => false  so break the second loop
arr[j+1] = candidateElement => arr[1+1] = 3 => arr[2] = 3



index
0
1
2
3
4
5
arr
1
2
3
5
8
6



Outer Loop 4th Iteration:


index
0
1
2
3
4
5
arr
1
2
3
5
8
6

i = 4
j = i-1 = 3
candidateElement = arr[i] =arr[4] =  8
arr[j] > candidateElement => arr[1] > 5 => 2 > 5 => false so break second loop
arr[j+1] = candidateElement => arr[3+1] = 8 => 8 remains at same position


Outer Loop 5th Iteration:


index
0
1
2
3
4
5
arr
1
2
3
5
8
6

i = 5
j = i-1 = 4
candidateElement = arr[i] =arr[5] =  6
arr[j] > candidateElement => arr[4] > 6 => 8 > 6 => true
arr[j+1] = arr[j] => arr[4+1] = arr[4] => arr[5] = arr[4]


index
0
1
2
3
4
5
arr
1
2
3
5
8
8

j-- => j-1=> 4-1 => 3
arr[j] > candidateElement => arr[3] > 6 => 5 > 6 => false so breaking the second loop
arr[j+1] = candidateElement = > arr[3+1] = 6  => arr[4] = 6
arr[] = 1 2 3 5 6 8


index
0
1
2
3
4
5
arr
1
2
3
5
6
8




Outer loop 6th Iteration:
index
0
1
2
3
4
5
arr
1
2
3
5
6
8
i = 6
i < size  => i < 6 => 6 < 6 => false so breaking the first loop

Method is executed completely and array has been sorted. 


 Thanks friends for reading this post, do leave comments below with your feedback.