Implementing Pigeonhole Sort in Java

Question

What is the simplest implementation of Pigeonhole Sort in Java? An array of array-lists is ideal, but Java makes this difficult if one wants to remain type-safe. Both an array of arrays or an array-list of array-lists can be used, but are somewhat awkward. I was wondering if there was a general recommendation for what data structure is best.

I would use a `LinkedList` since this performs insertion in *O(1)* whereas the amortized cost of an `ArrayList` insertion is *O(log n)* — Willem Van Onsem, Feb 14 '15 at 18:53

score 2 · Answer 1 · edited May 23 '17 at 11:49

First of all, if you want to achieve the theoretical computational complexity of pigeonhole sort, you should use a LinkedList<T> and not an ArrayList<T>. Many people forget that the amortized cost of insertion in an ArrayList<T> is O(log n) with n the number of elements in the list.

As you point out, there is a problem with creating an array of a generic(-dependent) type. But you can circumvent this using this answer.

So say n is the number of keys and f is a function calculating the key (maps to an integer between 0 and n-1 (inclusive)) on which we want to sort, then the (inline sorting) algorithm in Java 8 (with functional programming) looks like:

public static<T> void pigeonholeSort (T[] tosort, Function<T,Integer> f, int n) {
    LinkedList<T>[] holes = (LinkedList<T>[]) new LinkedList[n];
    for(int i = 0; i < n; i++) {
        holes[i] = new LinkedList<T>();
    }
    for(T t : tosort) {
        holes[f.apply(t)].add(t);
    }
    for(int i = 0, j = 0; i < n; i++) {
        for(T t : holes[i]) {
            tosort[j++] = t;
        }
    }
}

You can run this code for instance with:

String[] toSort = new String[] {"Foo","Bar","Baz","Fubar","Qux"};
pigeonholeSort(toSort,x -> (Integer) (x.charAt(0)-'A'),26);
System.out.println(Arrays.toString(toSort));

(on condition you only use strings that start with an uppercase Roman letter).

Implementing Pigeonhole Sort in Java

1 Answers1