Insertion Sort with example

Data Structure and Algorithm:

As we all know that "Data Structure and Algorithm" plays crucial role in computer science.

But if Java already provided a number of classes and APIs under collection framework to deal with it, why would we have to care about internal implementation.

After all Java is all about abstraction.

For example take Collections.sort() method which sorts elements as per natural or custom sorting order passed to method.

So why should we worry about internal implementation of Collections.sort() as below:

1. convert list to an array.

2. pass that array to Arrays.sort() method which uses merge sort algorithm to sort elements.

3. convert back sorted array to list.  

Well human civilization works on improvement. Who knows tomorrow you have some sorting algorithm which sorts elements faster than Arrays.sort() method with less memory requirement.

At the same by understanding internal implementation of data structure and its algorithm, we would be in better position to decide which data structure to be used in specific scenario to get optimum trade off between time and space.

As "Data Structure and Algorithm" is very vast topic, so it is not possible for me to cover everything about it with my small knowledge.

In this post, we will go through one of sorting algorithm called "Insertion Sort", its basic understanding and code implementation.

Insertion Sort:

Take real time example of playing cards. You arrange cards in your hand with respect to suits and ascending order.

So suppose you have 4 cards in you hand {4, 7, 8, J} and if next card is 5 then you put that card in between 4 and 7.

That's how Insertion Sort works. It says put the elements at its desired location as per order.

Pseudo code:

for i = 1 to length(A) - 1

    j = i

key = A[i]

    while j >= 0 and A[j-1] > key

        swap key and A[j-1]

        j = j - 1

Idea is, at end of every iteration all elements before nth element should be in sorted order. 

Here n represents position of key node which need to be put in sorted array.

Below diagram can explain in better manner:

Code:

 import java.util.Arrays;  
 public class InsertionSortExample {  
      public static void main(String[] args) {  
           int[] arr = {6,5,3,1,8,7,2,4};  
           InsertionSortExample sortUtil = new InsertionSortExample();  
           sortUtil.sort(arr);  
           System.out.println(Arrays.toString(arr));  
      }  
      public void sort(int[] arr){  
           int key;  
           for(int i=1; i<=arr.length-1; i++){  
                key = arr[i];  
                int j = i-1;  
                while(j>=0){  
                     if(key < arr[j]){  
                          arr[j+1] = arr[j];  
                          j--;  
                     }else{  
                          break;  
                     }  
                }  
                arr[j+1] = key;  
           }  
      }  
 }  

That's all from my end about Insertion Sort. Please let me know if you find any issues with topic and its explanation.