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:

• 1 < 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 1^st line 8 > 3, so 8 is shifted one cell to the right. 
In the 2^nd line 6 > 3, so 6 is shifted one cell to the right. 
In the 3^rd line 4 > 3, so  4 is shifted one cell to the right. 
In the 4^th 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.