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

float values[] = { 4, 1, 10, 9, 2, 5, -1, -9, -2,10000,-0.05,-3,-1.1 };

int compare (const void * a, const void * b)
{
    return ( (int) (*(float*)a - *(float*)b) );
}

int main ()
{

    int i;

    qsort (values, 13, sizeof(float), compare);

    for (i = 0; i < 13; i++)
    {
        printf ("%f ",values[ i ]);
    }
    putchar('\n');

    return 0;
}

结果是:

-9.000000 -3.000000 -2.000000 -1.000000 -1.100000 -0.050000 1.000000 2.000000 4.000000 5.000000 9.000000 10.000000 10000.0000000

这是错误的,因为 -1 和 -1.1 的顺序发生了变化。我相信它正在发生,因为我的“比较”功能。

我怎样才能解决这个问题?

谢谢

4

3 回答 3

40

您的比较功能已损坏。例如,它说-1.0等于(等价于)-1.1,因为(int) ((-1.0) - (-1.1))为零。换句话说,你自己告诉和qsort的相对顺序无关紧要。为什么您会惊讶于在结果排序中这些值没有排序?-1.0-1.1

通常,您应该避免通过将数值相减来比较数值。它只是行不通。对于浮点类型,由于很多不同的原因,它可能会产生不精确的结果,其中一个您刚刚观察到自己。对于整数类型,它可能会溢出。

比较两个数值a和看起来像b的通用习语。记住它并使用它。在你的情况下,那将是qsort(a > b) - (a < b)

int compare (const void * a, const void * b)
{
  float fa = *(const float*) a;
  float fb = *(const float*) b;
  return (fa > fb) - (fa < fb);
}

在 C 代码中,定义宏可能非常有意义

#define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))

并使用它而不是明确说明比较。

于 2010-10-07T22:56:47.173 回答
1

通过将差值四舍五入为整数,您将失去精度。

编辑:

修改比较函数为

return (*(float*)a >= *(float*)b) ? 1 : -1;

为 AndreyT 编辑:我不认为只返回1-1会导致无限循环或不正确的排序(它只会交换不需要的相等值)。

有一个明确的返回案例0将花费额外的浮点兼容性,而且它们很少相等。因此,如果输入数据中的碰撞率很小,则可以省略相等性比较。

于 2010-10-07T22:51:17.013 回答
0

要通过@AnT 添加到现有答案,您可以通过SortChecker自动验证您的qsort回调:

$ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out
a.out[7133]: qsort: comparison function is not transitive (comparison function 0x4005cd (/home/iuriig/a.out+0x4005cd), called from 0x400614 (/home/iuriig/a.out+0x400614), cmdline is "./a.out")
-9.000000 -3.000000 -2.000000 -1.000000 -1.100000 -0.050000 1.000000 2.000000 4.000000 5.000000 9.000000 10.000000 10000.000000

此警告表示compare报告x < y, y < z而不是x < z某些输入。要进一步调试此问题,请运行

export SORTCHECK_OPTIONS=raise=1

并检查生成的编码转储。

于 2018-04-26T09:03:03.600 回答