qsort的比较函数

缘起

之前实习时,同事遇到一个看起来诡异的bug,现象是用标准库的qsort函数得不到正确结果。 而同样的代码在别人电脑上却没有问题。一度怀疑是不是glibc的锅。

代码大概是这样的:

#include <stdlib.h>
int cmp(const void *a, const void *b)
{
    return *((int *)a) > *((int *)b);
}

int main()
{
    int array[] = {4, 2, 5, 2, 4, 67, 3, 5, 2, 4};
    qsort(array, sizeof(array)/sizeof(int), sizeof(int), cmp);

    return 0;
}

平时C写得多的同学估计一眼就看出来问题所在了。cmp函数中,a和b之间不应该用大于号比较,因为qsort函数是通过cmp函数返回正/负/零来判断元素间大小关系的。而由于C语言的隐式类型转换,上述cmp函数只会返回0或1。

不难总结,在a >= b时,这个错误的cmp函数会返回正确的结果。 同时反向思考,cmp返回1时,可以保证a > bcmp返回0时,a可能小于b,也可能等于b。

综上,cmp > 0a > b的充要条件。cmp = 0a = b的必要不充分条件,同时也是a <= b的充要条件。

所以排序得到错误结果也在意料之中了。

但是这段错误的代码为何在其他人的电脑上却可以得到正确结果呢?

这就取决于不同库对qsort的实现了。不同标准库内部实现是可以不同的,虽然能保证它们在正确情况下有相同表现,但是错误情况下,返回什么结果就都是未定义的了。 然而有意思的是,为什么有些库可以得到正确结果?是特定数据下的一种巧合么?

正确输入得到错误输出,需要问问为什么。错误输入却得到正确输出,更要问问为什么!

谜底

首先解释一下同事为何会犯这么常识性的错误。 他之前一直写的是C++,而C++中std::sort函数传入的comparator返回的是bool型,因此在C++中这么写是没有问题的,便把C++中的习惯带到了C语言中。

STL中的sort只需要返回bool值的comparator就可以进行排序,所以qsort要求返回正/负/零三种值显然是存在信息冗余的。毕竟快速排序法只需要对数组进行二分,而不是三分。

因此,有些库采取了类似std::sort的实现方式(std::sort默认使用std::less进行比较),只考察a是否大于b,而如前文所说,此时cmp > 0a > b的充要条件,即此错误的cmp函数和正确的comparator函数行为一致,所以可以得到正确的结果。

同时,前面说了,并不保证所有库都是这么实现,并且qsort函数一般不止使用快速排序这一种算法,在递归深层,可能还会使用插入/选择排序法。因此能得到正确的结果真是非常巧了(如果库作者当初就料想到有人会传入这种错误的comparator而刻意这么实现,我一点都不佩服他,因为正确的做法应该是对于错误的输入就及时报错)。

结语

可见,C语言的隐式类型转换以及未定义行为真是“可怕”,以及一些存在历史遗留问题的库函数(譬如你知道getchar的返回值是什么?),都是滋生bug的温床。但事实上这些bug也挺有意思,多关注关注这些问题,是通往“伪专家”的捷径。

最后留道思考题:

编写一个qsort实现,在传入上述错误的cmp函数的情况下也能排序得到正确结果。

更进一步,如果不是return *((int *)a) > *((int *)b);而是return *((int *)a) >= *((int *)b);,刚才的代码依然work么?


Powered by Jekyll and Theme by solid