Radix Sort Float

Question

I am trying to sort floats with radix. My current algorithm works with unsigned. For example, if I enter values 12, 100, 1 my sorted values are 1, 12, and 100. However, when I use a function to convert floats to ints back to floats after calling the radix sort, my values remain unsorted. They print as they were entered by the user.

I am unsure how to modify my current function to be able to sort floats with radix.

void rs(unsigned int *a, int c) {
    int i;
    int m = a[0];
    int bt = 0;
    unsigned int *b = malloc(0 * sizeof(int));

    for (i = 0; i < c; i++) {
        if (a[i] > m)
            m = a[i]; 
    }

    while((m>>bt) > 0){ 
        int buck[2] = { 0 };

        for (i = 0; i < c; i++) { 
            buck[(a[i]>>bt)&1]++;
        }

        for (i = 1; i < 2; i++) { 
            buck[i] += buck[i-1];
        }

        for (i = c-1; i >= 0; i--) { 
            b[--buck[(a[i]>>bt)&1]] = a[i]; 
        }

        for (i = 0; i < c; i++) {
            a[i] = b[i]; 
        }
        bt++;
    }
    free(b); 
}

The function I am using to transform floats to ints to floats is: Radix Sort for Floats

void rfloat(float* arr, size_t size) {
    assert(sizeof(unsigned) == sizeof(float) && sizeof(float) == 4);
    unsigned* d = malloc(size * sizeof(unsigned));
    
    for (size_t i = 0; i < size; i++) {
        // Interpret float as 32-bit unsigned.
        d[i] = *(unsigned*) &(arr[i]);

        // Flip all except top if top bit is set.
        d[i] ^= (((unsigned) (((int) d[i]) >> 31)) >> 1);

        // Flip top bit.
        d[i] ^= (1u << 31);
    }
    
    rs(d, size);
    
    // Inverse transform.
    for (size_t i = 0; i < size; i++) {
        d[i] ^= (1u << 31);
        d[i] ^= (((unsigned) (((int) d[i]) >> 31)) >> 1);
        arr[i] = *(float*) &(d[i]);
    }
    
    free(d);
}

Answer 1

There's multiple issues.

1. You use int all over the place where you should be using unsigned (for values) or size_t (for sizes/indices).

2. You allocate 0 bytes.

3. (m >> bt) > 0 doesn't work as a stop condition, shifting bits equal or greater than the width is not specified.

4. After transforming the data types to unsigned the loop boundaries don't work anymore.

I took the liberty of fixing the above and choosing some better variable names:

#include <limits.h>

void rs(unsigned int *a, size_t c) {
    size_t i;
    unsigned bit = 0;
    unsigned *b = malloc(c * sizeof(unsigned));

    unsigned m = a[0]; // Max element.
    for (i = 0; i < c; i++) {
        if (a[i] > m) m = a[i]; 
    }

    while (bit < CHAR_BIT*sizeof(m) && (m >> bit)) { 
        size_t bucket_len[2] = { 0, 0 };
        for (i = 0; i < c; i++) bucket_len[(a[i] >> bit) & 1]++;

        size_t bucket_end[2] = {bucket_len[0], bucket_len[0] + bucket_len[1]};
        for (i = c; i-- > 0; ) {
            size_t j = --bucket_end[(a[i] >> bit) & 1];
            b[j] = a[i]; 
        }

        for (i = 0; i < c; i++) a[i] = b[i]; 
        bit++;
    }
    
    free(b); 
}