Cygwin GCC qsort 函数错误

目录 开源, 算法, 编程

我平时在 Windows 下写代码时,经常使用 Cygwin 的 gcc。但是今天我居然发现 Cygwin 下 gcc 的 qsort 函数是错误的!这种基本的函数出错,太让人惊讶了。为了验证是不是代码有错,我使用 tcc 和 Linux 下的 gcc 都编译了同样一段程序,它们两个都输出了期望的结果,只有 Cygwin 的 gcc 是错的。下面是示例代码:

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

int compare(const void *p, const void *q)
{
  return *(const char *)p > *(const char *)q;
}

int main()
{
  char a[] = "1312515";
  printf("%sn", a);
  qsort(a, strlen(a), sizeof(char), compare);
  printf("%sn", a);
  return 0;
}

按说它应该输出:

1312515
1112355

但是我用 Cygwin gcc 编译后,它居然运行出这样的结果:

1312515
2111355

太诡异了。我尝试调试它,结果 gdb 无法步入 qsort 代码中。谁能告诉我是为什么?

附 Cygwin gcc 信息:

$ gcc -v
Using built-in specs.
Target: i686-pc-cygwin
Configured with: /gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2/configure --srcdir=/gnu/gcc/package/gcc4-4.3.2-2/src/gcc-4.3.2 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin --sbindir=/usr/sbin --libexecdir=/usr/sbin --datadir=/usr/share --localstatedir=/var --sysconfdir=/etc --infodir=/usr/share/info --mandir=/usr/share/man --datadir=/usr/share --infodir=/usr/share/info --mandir=/usr/share/man -v --with-gmp=/usr --with-mpfr=/usr --enable-bootstrap --enable-version-specific-runtime-libs --with-slibdir=/usr/bin --libexecdir=/usr/lib --enable-static --enable-shared --enable-shared-libgcc --enable-__cxa_atexit --with-gnu-ld --with-gnu-as --with-dwarf2 --disable-sjlj-exceptions --enable-languages=ada,c,c++,fortran,java,objc,obj-c++ --disable-symvers --enable-libjava --program-suffix=-4 --enable-libgomp --enable-libssp --enable-libada --enable-threads=posix AS=/opt/gcc-tools/bin/as.exe AS_FOR_TARGET=/opt/gcc-tools/bin/as.exe LD=/opt/gcc-tools/bin/ld.exe LD_FOR_TARGET=/opt/gcc-tools/bin/ld.exe
Thread model: posix
gcc version 4.3.2 20080827 (beta) 2 (GCC)

我犯了一个愚蠢的错误,感谢来自 Stephen 的评论

你的compare函数有问题,你的compare函数不会返回负数。修改compare为:
int compare(const void *p, const void *q)
{
return *(const char *)p - *(const char *)q;
}
再编译运行就正确了。

长按识别二维码关注《边际效应》
长按识别二维码关注《边际效应》

6 条评论

  • Stephen
    2009-10-14

    你的compare函数有问题,qsort要求的compare函数是这样的:
    如果p比q大,返回一个大于0的整数,如果p比q小,返回一个小于0的整数,如果p=q,返回0。你的函数不满足最后一点。修改compare为:
    int compare(const void *p, const void *q)
    {
    return *(const char *)p - *(const char *)q;
    }
    再编译运行就正确了。

  • Stephen
    2009-10-14

    @Stephen
    上面说错了一个小地方,你的compare函数不会返回负数,也就是p小于等于q时,返回的都是0.

  • Solrex Yang
    2009-10-14

    @Stephen
    哦,看来我对 compare 函数的理解有问题。我一直以为它只要能保持一个偏序就可以了,想当然的以为 > 号可以做这件事情。经过你一说,确实是这样,> 只能返回 0 和 1,不能返回负数,非常感谢。

  • Stephen
    2009-10-14

    @Solrex Yang
    我印象中标准C库中的所有比较函数都是这样要求的,比如strcmp等。qsort的有些实现中只用到偏序即可,有些实现则不一定。我看过VS的,glibc的还有uclibc的qsort实现,貌似都只用偏序就行了,还真没在意到cygwin这么诡异,哪天有空了也去找源码看看。

  • Cygwin GCC qsort 函数错误(续) | Solrex Shuffling
    2009-10-16

    [...] 上一篇文章中提到我在为 qsort 写 compare 函数时犯了一个愚蠢的错误:我脑袋陷入了一个错误的逻辑,以为 compare 函数嘛,就是要 compare 一下,那么我用 '>' 或者 '< ' 这种比较算符就可以满足要求(潜意识里认为 > 会返回 1 或者 -1,显然是错的,上篇文章的评论者 Stephen 开始也犯了同样的直觉错误,不过他马上就醒悟过来了)。我当时脑袋里也犹豫了一下要不要处理相等的情况,后来想快排算法中没有判断相等的情况,那么我没必要加上等号。 [...]

  • xiaojie
    2010-04-12

    今天重新看qsort,发现那如果对一个double数组排序又不能定义偏序怎么办?
    double不能直接相减吧?
    int cmp(const void* p, const void *q)
    {
    return *(double*)p > *(double*)q?1:-1;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注