Hackerrank Insertion Sort Part 2

Question

I have started learning Java recently and was looking into the challenges on sorting on Hackerrank.I solved the following problemHackerrank on Insertion Sort.

The challenge was :

In Insertion Sort Part 1, you sorted one element into an array. Using the same approach repeatedly, can you sort an entire unsorted array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an element with just the first element - that is already "sorted" since there's nothing to its left that is smaller.

In this challenge, don't print every time you move an element. Instead, print the array after each iteration of the insertion-sort, i.e., whenever the next element is placed at its correct position.

Since the array composed of just the first element is already "sorted", begin printing from the second element and on.

Input Format There will be two lines of input:

• the size of the array
• a list of numbers that makes up the array

Output Format : On each line, output the entire array at every iteration.

Sample Input:

6 1 4 3 5 6 2 

Sample Output:

 1 4 3 5 6 2 1 3 4 5 6 2 1 3 4 5 6 2 1 3 4 5 6 2 1 2 3 4 5 6 

I am trying to get better at writing good code for my solutions..Please give me your suggestions .

import java.util.Scanner; public class InsertionSortPart2 { public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); int size = keyboard.nextInt(); int[] array = new int[size]; for (int i = 0; i < array.length; i++) { array[i] = keyboard.nextInt(); } array = insertionsort(array); } private static int[] insertionsort(int[] a) { for (int i = 1; i < a.length; i++) { // set key to value at index i int key = a[i]; // set j as i-1 to look for previous element int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; for (int f = 0; f < a.length; f++) { System.out.print(a[f] + " "); } System.out.println(); } return a; } } 

Answer 1

Your code is pretty good. The biggest problem is consistent indentation. Everything inside of your class should be indented one level; this includes the main method and your insertionsort method.

private static int[] insertionsort(int[] a) { for (int i = 1; i < a.length; i++) { // set key to value at index i int key = a[i]; // set j as i-1 to look for previous element int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; for (int f = 0; f < a.length; f++) { System.out.print(a[f] + " "); } System.out.println(); } return a; } 

Indented better:

private static int[] insertionsort(int[] a) { for (int i = 1; i < a.length; i++) { // set key to value at index i int key = a[i]; // set j as i-1 to look for previous element int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; for (int f = 0; f < a.length; f++) { System.out.print(a[f] + " "); } System.out.println(); } return a; } 

---

Good job on making the insertionsort function static. However, Java's naming convention is camelCase: insertionSort. I could have misread it as insert ions ort and gotten confused.

---

private static int[] insertionsort(int[] a) {

The fact that you are returning an int[] makes it appear as if you don't modify the input array a (which would be better named toSort); however, you modify a and then return it. I strongly recommend either doing one or the other. If you don't want to modify the input, then you could do it as follows:

private static int[] insertionSort(int[] toSort) { int[] a = Arrays.copyOf(toSort, toSort.length); // needs to import java.util.Arrays 

If you do want to modify the input, I would declare the method it as follows:

private static void insertionSort(int[] a) { 

---

Additionally, your sort function should only sort, not print.

Here's the final result

private static void insertionSort(int[] toSort) { for (int i = 1; i < toSort.length; i++) { // set key to value at index i int key = toSort[i]; // set j as i-1 to look for previous element int j = i - 1; while (j >= 0 && toSort[j] > key) { toSort[j + 1] = toSort[j]; j--; } toSort[j + 1] = key; } } 

---

Going further

Insertion sort is a nice sorting algorithm that works for much more than just ints; you can sort doubles, BigIntegers, or even user-defined objects. Why not generify the function? You could do the following:

private static <T extends Comparable<T>> void insertionSort(T[] toSort) { for (int i = 1; i < toSort.length; i++) { // set key to value at index i T key = toSort[i]; // set j as i-1 to look for previous element int j = i - 1; while (j >= 0 && toSort[j].compareTo(key) > 0) { toSort[j + 1] = toSort[j]; j--; } toSort[j + 1] = key; } } private static <T> void insertionSort(T[] toSort, Comparator<T> compare) { for (int i = 1; i < toSort.length; i++) { // set key to value at index i T key = toSort[i]; // set j as i-1 to look for previous element int j = i - 1; while (j >= 0 && compare.compare(toSort[j], key) > 0) { toSort[j + 1] = toSort[j]; j--; } toSort[j + 1] = key; } } 

This should allow you to sort arbitrarily typed arrays, except for the primitive types, unfortunately (although I did not compile the code).

Answer 2

Your implementation is quite fine. Some minor improvements are possible.

The insertionsort method doesn't need to return the array. It's not required by the problem, and it's pointless anyway, as the method modifies the input array.

In the main method you called the array array. That's not a very useful name, too generic. Inside insertionsort it's even worse just the letter a. A better name in both places would be for example nums.

The inner while loop would be better as a for loop. The reason is, with a for loop it's easier to not forget to decrement the loop variable:

for (; j >= 0 && nums[j] > key; --j) { 

Also, you set j = i - 1, and then you have to remember to use a[j + 1] in two places. It would be slightly simpler to use j = i and rearrange the rest accordingly.

Lastly, the printing of the array really belongs to a separate helper method.

Answer 3

• No naked loops

  The inner loop implements an insert algorithm, and deserves a name. Factor it out into a method.

  It may or may not incur a performance penalty; I don't know how good Java is with function call inlining. With C I wouldn't think twice.

• Insertion

  The loop condition j >= 0 && a[j] > key checks for valid index on each iteration. Consider splitting insertion into 2 branches:

  if (a[0] > key) { shift_right_by_one(a, i); a[0] = key; } else { // This loop shall also become a method `unguarded_insert` while (a[j] > key) { a[j + 1] = a[j]; --j; } } 

  The while loop is known as unguarded insertion: since we ensure that a[0] < key the loop is guaranteed to terminate correctly, and uses twice as less comparisons.