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 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.