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?

Why not just sort the `float`s themselves? No need to convert to `int` or `String`. — Jorn, May 15 '23 at 13:19
@Jorn How would I go about doing that? I thought they had to be `int`s because radix sort only handles integers. I converted it to `String` to find the longest decimal places. — benkyou, May 15 '23 at 13:29

dan1st · Accepted Answer · 2023-05-15T19:24:50.340

2

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.

edited May 15 '23 at 19:24

answered May 15 '23 at 13:31

dan1st

12,568
8
34
67

It could (isn't that pretty much what I have said in my answer?) - but to be honest, I don't think it would be faster than e.g. quicksort in practice as you probably don't have that many numbers to sort (you have to maintain all of the queues etc.). However, measure, don't guess! – dan1st May 15 '23 at 19:19
The OP is using `Queue`s for their radix sort implementation and having a `List` of `Queue`s _might_ harm locality (and boxed types are not that efficient as well). – dan1st May 15 '23 at 22:33
Also, you need to at least pass through the whole mantissa for floating point numbers before reaching the exponent whereas you might be able to skip later iterations for integers if the values are relatively low (depending on the use-case). – dan1st May 15 '23 at 22:42
There's the option of doing one most significant digit first, normally used to get each "bucket" to fit within cache. [Example code](https://stackoverflow.com/a/44792724/3282056). In this case, the first digit could be 12 bits (sign bit, which in this case is 0, and exponent). – rcgldr May 16 '23 at 02:10
And how is that relevant to the question? The OP is not doing that. – dan1st May 16 '23 at 13:19
The OP usage of queues is inefficient, but I don't see a significant difference between using the OP's implementation for longs, versus using it for doubles converted to longs. I deleted my prior comments. – rcgldr May 16 '23 at 15:41
For `int`s, there might be the case where all of the numbers to sort are e.g. <1024. In such cases, you could skip all passes after that point. For `double`s, this would not work so easily as one would hit a non-zero exponent. However, I meant this as something that _could_ happen which needs to be tested on a case-per-case basis. – dan1st May 16 '23 at 16:34
If the doubles were all integers in the range 0 to 1024, then the bottom 40 bits would be zero, and similar logic could be used to skip the passes before reaching the 40th bit. – rcgldr May 16 '23 at 20:36

LSD radix sort in Java for positive floating points

1 Answers1