Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Insertion sort implementation in Java

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 754
    Comment on it

    Hi Readers,

    This blog is to help you to understand how insertion sort works. Insertion sort is a simple sorting algorithm which is good to sort short list.

    Real life example of insertion sort is sorting of playing cards, Like we pick a card and put it where it should come. Same process is repeated until all cards are in sorted order.

    Insertion sort have simpler implementation and is efficient to sort small list of elements. Average case time complexity of Insertion sort is O(n*n).

    In our below approach considering elements as cards we pick from second card to the last card in order.

    As we picked the 2nd card it has to be matched to the previous card until picked card is greater than the previous one. Now that card will be placed after that element which had lesser value than the picked one. Now 3rd card will be picked and will be placed to its correct location. Cards has to be picked successively until we traversed the last card in hand.

    Java Implementation for Insertion sort.

    public class InsertionSortDemo {
    
    	private static void insertionSort(int arr[]) {
    		int len = arr.length;
    		int temp;
    		int j;
    		for (int i = 1; i < len; i++) {
    			if (arr[i] < arr[i - 1]) {
    				// System.out.println("true");
    				temp = arr[i];
    				j = i;
    				while (j > 0 && (temp < arr[j - 1])) {
    					arr[j] = arr[j - 1];
    					j--;
    				}
    				arr[j] = temp;
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		int[] arr = { 10, 4, 2, 1, 325, 64, 57, 31, 2, 34, 5, 41, 674, 5, 83,
    				47, 8, 5, 14, 3, 25, 8, 34, 756 };
    		System.out.println("Before Sort");
    		for (int i : arr)
    			System.out.print(i + " ");
    		System.out.println("\n");
    
    		insertionSort(arr);
    		System.out.println("After  Sort");
    		for (int i : arr)
    			System.out.print(i + " ");
    		System.out.println();
    	}
    }

     

    After running the above code output will be like this

    Before Sort
    10 4 2 1 325 64 57 31 2 34 5 41 674 5 83 47 8 5 14 3 25 8 34 756 
    
    After  Sort
    1 2 2 3 4 5 5 5 8 8 10 14 25 31 34 34 41 47 57 64 83 325 674 756 

     

    Thanks for reading.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: