Insertion Sort implementation in Java

One of the simplest (in terms of understanding :P) sorting technique is Insertion Sort.
You will find many sites giving example of cards. Like suppose left hand has already sorted cards where as right hand has unsorted. You can pick first card from right hand unsorted and try to put it in left hand so that the sorted order preserves in left hand.

Suppose you never played card in your life (means you wasted your childhood 😛 ).
You can also think of 2 queue of people ( A and B). In queue A, all the people are standing in incremental order of their height and in queue B, no one gives a shit about any order. Now suppose a person P from queue B is tired of those people and wants to join queue A. So when he join queue A, he has to start from the person who is standing last and find a position so that the order of height preserves. In this process all the people from queue A who are taller than P, has to shift their place one step back.

Now lets implement this in java using ArrayList.

My project Explorer:

 

InsertionSortProjectExplorer

 

InsertionSort.java

package daa;

import java.util.ArrayList;

public class InsertionSort {	

	private static ArrayList<Integer> inputArray = new ArrayList<Integer>();

	public static ArrayList<Integer> getInputArray() {
		return inputArray;
	}

	//Just for the display purpose
	public InsertionSort(ArrayList<Integer> inputArray){
		InsertionSort.inputArray = inputArray;
	}
	
	public void sortGivenArray(){					
		for(int i=1;i<inputArray.size();i++){
			
			int key = inputArray.get(i);
			
			for(int j= i-1;j>=0;j--){
				if(key<inputArray.get(j)){
					// Shifting Each Element to its right as key is less than the existing element at current index
					inputArray.set(j+1,inputArray.get(j));
					
					// Special case scenario when all elements are less than key, so placing key value at 0th Position
					if(j==0){
						inputArray.set(0, key);
					}
				}else{
					// Putting Key value after element at current index as Key value is no more less than the existing element at current index
					inputArray.set(j+1,key);
					break; // You need to break the loop to save un necessary iteration
				}
			}
		}		
	}
}

 

 

MainPractise.java

import java.util.ArrayList;

import daa.InsertionSort;


public class MainPractise implements Cloneable {	
	
	public static void main(String[] args) {
		
		
		ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
		
		unsortedArray.add(8);
		unsortedArray.add(7);
		unsortedArray.add(6);
		unsortedArray.add(5);
		unsortedArray.add(4);
		unsortedArray.add(0);
		unsortedArray.add(2);	
		InsertionSort is = new InsertionSort(unsortedArray);
		
		System.out.println("---------Initial Unsorted Array---------");
		for(int i:InsertionSort.getInputArray()){
			System.out.print(i+" ");
		}
		
		is.sortGivenArray();
		
		System.out.println("\n------------Sorted Array------------");
		for(int i:InsertionSort.getInputArray()){
			System.out.print(i+" ");
		}
        }
}

 

Output:

———Initial Unsorted Array———
8 7 6 5 4 0 2
————Sorted Array————
0 2 4 5 6 7 8

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

If you have any question mail us on
snippetexample@gmail.com or Post comments or join us on facebook.


Leave a Reply

Your email address will not be published. Required fields are marked *