Recent Tutorials and Articles
HackerRank Solution: Insertion Sort 1
Published on: 25th May 2018

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

.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: 25th May 2018