Insertion sort implementation

Question

import java.util.Scanner;
import java.lang.Comparable;


class InsertionSort {
    private InsertionSort() {}

    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static void sort(Comparable[] a) {
        int length = a.length;
        for (int i = 0; i < length; i++) {
            // Maintain Invariant
            for (int j = i; j > 0; j--) {
                if (less(a[j], a[j - 1])) { // Invariant broken, fix it.
                    exch(a, j, j - 1);
                }
            }
        }
        // Postcondition: assert isSorted(a) 
    }

    private static void show(Object[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    private static Integer[] readAllInts() {
        Scanner scanner = new Scanner(System.in);

        int numberOfItems;
        Integer[] items;
        if (scanner.hasNext()) {
            numberOfItems = scanner.nextInt();
            items = new Integer[numberOfItems];         
        } else {
            // mybe throw an error?
            return new Integer[0];
        }

        int i = 0;
        while(scanner.hasNext() && i < numberOfItems) {
            items[i] = scanner.nextInt();
            i++;
        }
        return items;
    }

    public static void main(String[] args) {
        Integer[] items = InsertionSort.readAllInts();
        InsertionSort.sort(items);
        InsertionSort.show(items);
    }
}

Above is the implementation of the insertion sort algorithm. I want learn how to write algorithms as well Clean Code. Now below are the points which I have taken care of or am concerned about.

• Kept meaningful names.
• Declared variables near their usage.
• Suppose, this code needs to consumed by many clients then where and what exception I should handle and throw.
• Kept variable scopes to as local as possible for easy GC.
• Most of the methods are static because I don't think they belong to a particular object.

That's it for now, I will keep updating the list if something comes to me later.

Ref: Algorithms

Answer 1

readAllInts

This is a wishy washy name. What does it mean, "all ints"? In the universe? In my little black book of ints? Entered by the user on standard input? Aha!

It might be good to split this up to multiple methods:

• a method to read and return the number of ints from a scanner and handle errors: print a message in case of invalid input and try again, or simply throw an exception
• a method to read specified number of ints from a scanner and return as an array
• a method that calls the previous two and returns the array

That way each method will have a simpler, single responsibility.

A bigger problem with this method is that it doesn't belong in the InsertionSort class. The way you read an array of integers has nothing to do with the spring algorithm.

Type safety

By not using type tokens, you sacrificed type safety. For example a call less(4, "hello") would compile, which is undesirable.

You should never use bare types, always specify type parameters. For example you can make less type safe like this:

private static <T extends Comparable<? super T>> boolean less(T v, T w) {
    return v.compareTo(w) < 0;
}

This effectively prevents less(4, "hello") at compile time.

Correcting sort similarly:

public static <T extends Comparable<? super T>> void sort(T[] a) {
    int length = a.length;
    for (int i = 0; i < length; i++) {
        for (int j = i; j > 0; j--) {
            if (less(a[j], a[j - 1])) { // Invariant broken, fix it.
                exch(a, j, j - 1);
            }
        }
    }
}

And that's it, the other methods are fine, as they don't use bare types, and they are fine using Object[] for swapping and printing.

Naming

exch is not a great name. " exchange " would be better, but the most common name for this operation is "swap".

less is also not great, as some might interpret it in the sense of " minus ". I suggest "lessThan" instead, which makes the comparison logic perfectly clear.

The variable a is the worst offender of all. "swap" is not great either.

Answer 2

Speed up the sort

Here in the main part of your sort:

   for (int i = 0; i < length; i++) {
        // Maintain Invariant
        for (int j = i; j > 0; j--) {
            if (less(a[j], a[j - 1])) { // Invariant broken, fix it.
                exch(a, j, j - 1);
            }
        }
    }

Once you find the correct spot for a[i], you should immediately move on to the next item. Right now you swap it down to the correct spot and then keep looking at all the other items that are already sorted. So I would add a break statement like this:

    for (int i = 0; i < length; i++) {
        // Maintain Invariant
        for (int j = i; j > 0; j--) {
            if (less(a[j], a[j - 1])) { // Invariant broken, fix it.
                exch(a, j, j - 1);
            } else {
                break;
            }
        }
    }