基数浮点数 [英] Radix Sort for Floats

查看:120
本文介绍了基数浮点数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想对C中的浮点数进行基数排序.下面是我的代码.但是,我的输出不正确.例如,如果我用3.1,-5和1运行代码,则我的排序值将打印为3.000000,-5.000000和1.000000.

I want to sort floats in C with radix. Below is the code I have. However, my output is not correct. For example, if I run the code with 3.1, -5, and 1 my sorted values are printed as 3.000000, -5.000000, and 1.000000.

我知道要正确地从浮点数转换为int并转换回浮点数,我需要应用以下逻辑,但是由于我尝试了很多错误,因此我不确定如何将其集成到rfloat()中.

I know to cast correctly from a float to an int back to a float, I need to apply the following logic but I am not sure how to integrate this into rfloat() because I tried and am getting many errors.

我怎样才能正确地对浮点数应用按位基数排序?

How would I be able to correctly apply a bitwise radix sort to floats?

float x = 3.1, *y; 
    int *a; 
    
    a = (int *)&x; 
    y = (float *)a; 

    printf("%f",*y); 

#include <stdio.h>
#include <stdlib.h>

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); 
}

void rfloat(float *arr, int c) {
    int d[c]; 
    int i; 
    
    for(i = 0; i < c; i++){
        d[i] = (int)arr[i];
    }
    
    rs(d, c);
    
    for(i = 0; i < c; i++){
        arr[i] = (float)d[i]; 
    }
    
}

int main() {
    int size;  
    int i; 
    float* arr = malloc(0* sizeof(float)); 
    
    printf("Size: "); 
    scanf("%d", &size); 
    
    for (int i = 0; i < size; i++){
        printf("Values: ");
        scanf("%f", &arr[i]); 
    }
    
    rfloat(arr, size); 
    
    printf("Sorted: ");
    for (i = 0; i < size; i++){
        printf("%f ", arr[i]);
    }
    free(arr); 
}

推荐答案

正值浮点数的排序方式与您将其位模式排序为无符号整数时的排序方式相同.负浮点数不是,它们以反向的顺序进行排序,比起您对位模式进行排序的情况而言.此外,如果您要对正浮点数进行排序,则负浮点数会在之后排序,因为它们的最高位已设置.

Positive floats sort in the same order as they would if you would sort their bit pattern as unsigned integers. Negative floats do not, they sort in the reverse order than if you would sort their bit pattern. Furthermore, negative floats sort after the positive ones if you would sort on their bit pattern, because their top bit is set.

那我们该怎么办?我们进行转换.如果设置了最高位,则翻转所有其他位(使负数在它们之间正确排序),并且始终翻转最高位(以使负数和正数正确地排序).然后排序后,我们反转转换.

So what do we do? We do a transform. We flip all the other bits if the top bit is set (making negative numbers sort correctly between themselves), and we always flip the top bit (to make negative and positive numbers sort correctly). Then after sorting we reverse the transformation.

不需要四舍五入!

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);
}


请注意,此后您的代码仍然无法使用.您的基数排序例程有问题.但这是另一个问题,如果您自己无法弄清楚.


Note that your code still doesn't work after this. Your radix sort routine has issues. But that is for another question, if you can't figure it out yourself.

这篇关于基数浮点数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆