Recent Tutorials and Articles
    HackerRank Solution: Insertion Sort 1
    Published on: 4th August 2016

    This tutorial provides Java solution to "Insertion Sort 1" challenge of HackerRank.

    Hackerrank Challenge Details


    Problem Statement:

    Given a sorted list with an unsorted number e in the rightmost cell, can you write some simple code to insert e into the array so that it remains sorted?

    Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.

    Guideline: You can copy the value of e to a variable and consider its cell "empty". Since this leaves an extra cell empty on the right, you can shift everything over until V can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with e.

    Input Format:

    There will be two lines of input:

    • Size - the size of the array
    • Arr - the unsorted array of integers

    Output Format:

    On each line, output the entire array every time an item is shifted in it.

    Constraints:

    • < Size < 1000
    • -10000 < e < 10000, e € Arr

    Sample Input:

    5
    2 4 6 8 3

    Sample Output:

    2 4 6 8 8 
    2 4 6 6 8 
    2 4 4 6 8 
    2 3 4 6 8 

    Explanation:

    3 is removed from the end of the array.
    In the 1st line 8 > 3, so 8 is shifted one cell to the right. 
    In the 2nd line 6 > 3, so 6 is shifted one cell to the right. 
    In the 3rd line 4 > 3, so  4 is shifted one cell to the right. 
    In the 4th line 2 < 3, so 3 is placed at position 2

    Task:

    .Complete the method insertionSort which takes in one parameter:

    • Arr - an array with the value e in the right-most cell.

    Solution Details


    Java Implementation:

    package com.saintech.allprogtutorials.hackerrank.algos;
    
    import java.util.Scanner;
    
    /**
     * @author Sain Technology Solutions
     * 
     * Solution to Problem - https://www.hackerrank.com/challenges/insertionsort1
     *
     */
    public class InsertionSort1 {
    	
    	/**
    	 * Prints the all elements of input array.
    	 */
    	private static void printArray(int[] arr) {
    		for(int elem : arr) {
    			System.out.print(elem + " ");
    		}
    		System.out.println();
    	}
    	
    	/**
    	 * Inserts the last unsorted element of array to its right place to make it sorted.
    	 */
    	public static void insertIntoSorted(int[] elems) {
    		final int length = elems.length;
    		
    		// No movement of elements will be required if-
    		// 	- There is just one element in array
    		//	- Array is already sorted
    		if(length < 2 || elems[length - 2] < elems[length - 1]) {
    			return;
    		}
    		// Store the last element
    		final int unsortedNumber = elems[length - 1];
    		int i = length - 2;
    		// Keep shifting elements to right unless we meet a number less than unsorted number
    		for(; i >= 0 && elems[i] > unsortedNumber; i--) {
    			elems[i + 1] = elems[i];
    			printArray(elems);
    		}
    		// Replace the number with unsorted number
    		elems[i + 1] = unsortedNumber;
    		printArray(elems);
    	}
    	
    	public static void main(String[] args) {
    		final Scanner in = new Scanner(System.in);
    		final int N = in.nextInt();
    		
    		final int[] elems = new int[N];
    		for(int i = 0; i < N; i++) {
    			elems[i] = in.nextInt();
    		}
    		in.close();
    		
    		insertIntoSorted(elems);
    	}
    }
    

    Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.

    Published on: 4th August 2016