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.