Radix sort in Java

Question

As homework I had to implement many sorting algorithms including radix sort in Java. The task is to sort doubles in the range [0-1) that are rounded to the 10th decimal point.

I thought of 2 ways on doing radix sort, one using counting sort and another one using buckets. They both work but they are extremely slow compared to quick sort. On average quick sort takes 0.068 seconds on a 800,000 doubles array, and both radix sorts are around 0.36 second. Any suggestions on how I can optimize any of the algorithms?

Using counting sort:

public class RadixSort implements Sorter {
    private static final long BIG_NUM = (long) Math.pow(10, 10);

    @Override
    public void sort(double[] ar) {
        Container[] containers = new Container[ar.length];
        for (int i = 0; i < ar.length; i++) {
            containers[i] = new Container(ar[i]);
        }
        for (long j = BIG_NUM; j >= 10; j = j / 10) {
            for (int i = 0; i < ar.length; i++) {
                double temp = containers[i].source * j;
                if (j != BIG_NUM) {
                    temp = Math.floor(temp);
                }
                long temp2 = (long) (temp % 10) + 1;
                containers[i].forCountingSort = temp2;
            }
            containers = countingSort(containers, 10);
        }
        for (int i = 0; i < ar.length; i++) {
            ar[i] = containers[i].source;
        }
    }


    private Container[] createOutput(Container[] org) {
        Container[] output = new Container[org.length];
        for (int i = 0; i < org.length; i++) {
            output[i] = new Container();
        }
        return output;
    }

    /**
     * @param containers array of container objects.
     * @param maxVal     max value for the contingsort range;
     * @return new Container[] array partly sorted with Countingsort.
     */
    public Container[] countingSort(Container[] containers, int maxVal) {
        int[] c = new int[maxVal];
        Container[] b = createOutput(containers);
        for (int j = 0; j < containers.length; j++) {
            if (containers[j].forCountingSort != 0)
                c[(int) containers[j].forCountingSort - 1]++;
        }
        for (int j = 1; j < c.length; j++) {
            c[j] += c[j - 1];
        }
        for (int j = containers.length - 1; j >= 0; j--) {
            if (containers[j].forCountingSort != 0) {
                b[c[(int) containers[j].forCountingSort - 1] - 1].forCountingSort = containers[j].forCountingSort;
                b[c[(int) containers[j].forCountingSort - 1] - 1].source = containers[j].source;
                c[(int) containers[j].forCountingSort - 1]--;
            }
        }
        return b;
    }


    /*
    Object to keep track of the original double while using counting sort;
     */
    public static class Container {
        long forCountingSort;
        double source;

        public Container(double source) {
            this.source = source;
        }

        @Override
        public String toString() {
            return "source: " + source + "int: " + forCountingSort;
        }

        public Container() {
        }
    }

}

Using buckets:

public class newRadixSort implements Sorter {
    private static final long BIG_NUM = (long) Math.pow(10, 10);
    private ArrayList<Double>[] buckets = getBuckets();

    @Override
    public void sort(double[] ar) {
       /* iterates over the array 10*n times,
       each iteration in the inside loop it puts the double int a bucket according
       to it's corresponding digit.
        */
        for (long j = BIG_NUM; j >= 10; j = j / 10) {
            for (int i = 0; i < ar.length; i++) {
                int index = (int) ((ar[i] * j) % 10);
                buckets[index].add(ar[i]);
            }

            /*
            merges all the bucket's into the output array
            and empty the buckets for reuse
             */
            for (int n = 0; n < ar.length; n++) {
                for (int k = 0; k < buckets.length; k++) {
                    for (int h = 0; h < buckets[k].size(); h++) {
                        ar[n] = buckets[k].get(h);
                        n++;
                    }
                    buckets[k] = new ArrayList<>();
                }
                }
            }
        }


    }

    /**
     * creates 10 buckets for the sorting
     *
     * @return ArrayList<Double>[] with 10 buckets.
     */
    public ArrayList<Double>[] getBuckets() {
        ArrayList<Double>[] al = new ArrayList[10];
        for (int i = 0; i < al.length; i++) {
            al[i] = new ArrayList<>();
        }
        return al;
    }
}

Answer 1

In general, any math on doubles is slower than on integers. In addition, you have repeated downcasting from double to int which also incurs a hit.

You know your decimal value is up to 10 digits -- just a smidge too many digits to guarantee you can move the decimal and represent it as an int, but you can represent it as a long which is just as good because java and modern hardware architectures are 64 bits. So, any math on them will be really fast.

Why not convert the decimal to a long

Math.floor(d * 10000000000L)

by shifting the digits left, performing your digit selection and bucket sorting, then outputting them back in decimal form? Like, take your random set and first convert all of them.

I would expect better overall execution time.