Insertion sorting an int array

Question

I'd like to improve this Insertion sort code

package com.arun.sort;

import java.util.Arrays;

public class InsertionSort {

public static void main(String[] args) {

    int[] arr = { 9, 4, 6, 2, 1, 7 };

    insertionSort(arr);
    System.out.println("Elements after sorting :" + Arrays.toString(arr));

}

public static int[] insertionSort(int[] arr) {

    int value, hole;

    for (int i = 1; i < arr.length; i++) {
        value = arr[i];
        hole = i;

        while (hole > 0 && arr[hole - 1] > value) {
            arr[hole] = arr[hole - 1];
            hole--;
        }

        arr[hole] = value;
    }
    return arr;
   }
 }

Answer 1

Step 1: extract to a method

In the current code you have a hardcoded array, and the main logic follows right after. It's hard to test this way. What if you want to see if the implementation works with a different set of numbers? You have to rewrite the array. Better to extract the main logic into its own, independent method:

int[] sort(int[] arr) {
    // ...
}

Now you can test with multiple different inputs easier:

arr = new int[]{2, 5, 1, 8, 12, 3, 7};
InsertionSort.sort(arr);
System.out.println(Arrays.toString(arr));

arr = new int[]{4, 3, 2, 1, 2};
InsertionSort.sort(arr);
System.out.println(Arrays.toString(arr));

Step 2: convert print statements to proper unit tests

The problem with print statements is that every time you change something and rerun, you have to re-verify the output of each statement. Unit tests can automate the verification step, and converting is easy enough to do:

private void sort(int[] arr) {
    InsertionSort.sort(arr);
}

@Test
public void testMixedValues() {
    int[] arr = {2, 5, 1, 8, 12, 3, 7};
    sort(arr);
    assertEquals("[1, 2, 3, 5, 7, 8, 12]", Arrays.toString(arr));
}

@Test
public void testDecreasingValues() {
    int[] arr = {4, 3, 2, 1};
    sort(arr);
    assertEquals("[1, 2, 3, 4]", Arrays.toString(arr));
}

Btw, I didn't type the expected strings in the assertEquals. I wrote the test cases first, with "" as the expected values, and ran the tests. All the tests failed, of course, but the error messages told me the actual values that were different from the expected "". I verified that they are correct and copy-pasted the correct texts into the test cases.

Now you can make changes and the test cases will flag an error if something breaks. Unless you do something really horrible, typically only a few of the test cases will break, and you don't need to reverify the others that are still working, which makes debugging a lot easier.

Return void instead of int[]

It might be better to return void instead of int[]. The problem with returning int[] is that the caller might wonder if the returned array is a new array or not. It is not a new array. For example in this code:

int[] arr1 = { 9, 4, 6, 2, 1, 7 };
int[] arr2 = InsertionSort.sort(arr1);
arr2[3] = -1;

Both arr1 and arr2 will be modified, which might be counter-intuitive.

The fact that java.util.Collections.sort() also returns void suggests that it's better that way.

Minor things

The method name insertionSort is redundant, because the word "insertion" is already in the class name. How about simply sort?