使用C语言qsort函数遇到问题

Question

#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.000000

这个结果是错的，因为-1和-1.1的顺序被改变了。 我相信这是由于我的“比较”函数导致的。

我该如何解决这个问题？

谢谢

- Luiz Fernando

---

qsort 运行正常。你对 qsort 的调用 是有问题的。 - aaronasterling

Answer 1

你的比较函数有问题。例如，它认为-1.0等于（等价于）-1.1，因为(int) ((-1.0) - (-1.1))为零。换句话说，你告诉qsort相对顺序不重要。为什么在排序后这些值没有被排序会让你惊讶？

一般来说，避免通过相减进行数值比较。它不起作用。对于浮点类型，由于多种原因，可能会产生不精确的结果，其中之一就是你已经观察到的情况。对于整数类型，可能会溢出。

对于qsort比较两个数值a和b的通用语法如下：(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)))

使用它代替明确拼写比较。

- AnT stands with Russia

---

+1 需要更多的赞同，这应该被接受为答案。 - Jared Burrows

return (fa > fb) - (fa < fb) 是优雅的写法，但是 return (fa < fb) ? -1 : (fa > fb); 可能更快。具体情况可能因人而异。 - chux - Reinstate Monica

@chux：为什么会更快？ - AnT stands with Russia

@chux：只有低质量的编译器才会在执行(fa > fb) - (fa < fb)时进行两次比较。大多数CPU使用设置特定CPU状态标志的CPU指令来比较值。这些状态标志完全描述了比较的结果。单个fa vs. fb比较生成覆盖fa和fb之间所有关系比较的标志。也就是说，一个比较立即为fa > fb和fa < fb提供了答案。所需的只是从CPU标志中提取这些结果并执行减法运算。 - AnT stands with Russia

@chux：你的 (fa < fb) ? -1 : (fa > fb) 可能会分支。它分支的事实表明它可能会变得更慢。 - AnT stands with Russia

Answer 2

将差异四舍五入为整数会导致精度损失。

编辑：

修改比较函数为

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

针对AndreyT的编辑：我认为仅返回1或-1不会导致无限循环或错误排序（它只会交换不需要的相等值）。

显式返回0的情况会增加一个浮点计算，而它们很少相等。因此，如果输入数据中的冲突率很小，则可以省略相等性比较。

- ruslik

---

无法正常工作。此函数将对相等的值返回“-1”，这意味着对于相等的“a”和“b”，比较“a”和“b”将表明“a < b”，但比较“b”和“a”将表明“b < a”。使用这样的比较函数，qsort将无法正确工作。 - AnT stands with Russia

你的编辑没有改变任何东西，除了现在相等的值将始终返回1。标准的qsort是为一个三值函数比较器设计的。无论你做什么，通常不可能将其简化为一个二值函数。你必须返回-1, 0, +1。 - AnT stands with Russia

qsort 的调试实现检查比较函数的正确性并不罕见。如果您的比较函数对 (a, b) 的比较返回 1，同时对 (b, a) 的比较也返回 1，这种调试版本的 qsort 通常会立即中止并出现断言错误。非调试实现则会产生未定义的行为。 - AnT stands with Russia

Answer 3

对于@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

并检查生成的代码转储。

- yugr