One of the simplest (in terms of understanding :P) sorting technique is Insertion Sort.
You will find many sites giving an example of cards. Like, suppose left hand has already sorted cards where as the right hand has unsorted. You can pick the first card from right hand unsorted and try to put it in the left hand so that the sorted order preserves in the left hand.
Suppose you never played cards in your life (means you wasted your childhood 😛 ).
You can also think of 2 queues 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 joins 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 let’s implement this in java using ArrayList.
My project Explorer:
InsertionSort.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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:
|
1 2 3 4 |
---------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.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git
If you have any question email us on
snippetexample@gmail.com or Post comments or join us on Facebook.