LSD radix sort in Java for positive floating points

Question

I am implementing radix sort using queues. As of now, it works for sorting integers, but I want to modify it to sort positive floating points as well.

public static void radixSort(int[] array) {
    int max = getMaxElement(array);

    List<Queue<Integer>> queues = new ArrayList<>(10);

    for (int i = 0; i < 10; i++)
        queues.add(new LinkedList<>());

    /* insert into queues based on radix */
    for (int exp = 1; max / exp > 1; exp *= 10) {
        for (int value: array) {
            int digit = value / exp % 10;
            queues.get(digit).add(value);
        }
    } 

    /* dequeue into original array */
    int index = 0;
    for (int i = 0; i < 10; i++) {
        while (!queue.get(i).isEmpty())
            array[index++] = queues.get(i).remove();
    }
}

I tried by finding the longest decimal places then multiplying each element in the array by 10 raised to the power of it so that the floating points can be sorted as integers. However, the method I used would require converting them to strings to find the . longest decimal places. Is there a more elegant way for sorting floating points?

Answer 1

Floating point numbers can go over a wide range (they could be very close or very far from zero) so I would not use that approach. Instead, you could sort by sign, exponent and mantissa:

You could try using the binary representation. You can convert a floating point number to its binary representation using Double#doubleToRawLongBits or similar.

Then, you can extract the sign part, exponent and mantissa:

double yourNumber=13.37;
long longRepresentation=Double.doubleToRawLongBits(yourNumber);
long sign=longRepresentation&0x8000000000000000L;
long exponent = longRepresentation&0x7ff0000000000000L;
long mantissa = longRepresentation&0x000fffffffffffffL;

Observe that if the long representation of one number is greater than the other, the same holds for the corresponding floating point numbers.

The sign is at the same position as it would be for long values. Also, the exponent (which is more significant than the mantissa) is in the significant position. So, you could just sort the long representations instead of the actual doubles. However, you should make sure that your sorting algorithm really works for negative numbers as well.

Since you probably don't want to call Double#doubleToLongBits over and over, you might want to first convert your data longs first, then sort them and finally convert them back:

public static void radixSort(double[] array) {
    long[] longArray=new long[array.length];
    for(int i=0;i<array.length;i++){
        longArray[i]=Double.doubleToRawLongBits(array[i]);
    }
    radixSort(longArray);
    for(int i=0;i<array.length;i++){
        array[i]=Double.longBitsToDouble(longArray[i]);
    }
}

It shall be noted that it is very likely not efficient to use radix sort for long values due to their structure. Sorting algorithms based on comparison are probably more efficient if you don't have that many numbers to sort.