C++ qsort是否曾将元素与自身进行比较？

Question

我需要使用qsort稳定排序数组.为了确保结果稳定,我在比较函数中添加了一个额外条件:

int compare(const void *p1, const void *p2)
{
    if(*(const Data*)p1 < *(const Data*)p2)
        return -1;
    if(*(const Data*)p2 < *(const Data*)p1)
        return 1;
    else
        return p1<p2 ? -1 : 1;
}

如果qsort从不调用compare(p,p),这将有效.否则我需要使用更复杂的条件.问题是,qsort是否曾经使用重复指针调用compare(),还是总是比较不同的指针？

更新:

我用Ideone C++编译器检查了这个:https://ideone.com/l026kM

对于注释中的小例子{8,8,1,1},提供的qsort()实现不会改变指针的顺序,也不会为同一元素调用compare.这似乎是合理的,因为每次反向交换都会影响性能,因为它需要稍后进行交换.我将使用随机生成的数组和不同的编译器来测试它.

更新:

在Ideone上测试100000个随机数组,重复键的最小份额为80%.结果是100%稳定的排序数组.这是链接:https://ideone.com/KOYbgJ

VC++ Express 2008编译器无法稳定排序,因为指针的顺序已更改.这基本上说明了VC++实现与GCC实现的不同之处在于它不保持指针顺序.

Answer 1

任何未明确禁止的内容都是隐含允许的; 特别是,我记得调试版本中的VC++在实际执行之前在同一元素(以及其他健全性测试)中明确地测试了比较器std::sort.不知道它是否也一样qsort,但它被允许.

但最重要的是,您的比较器违反了规定的要求qsort; 特别是:

当相同的对象(由size字节组成,不管它们在数组中的当前位置)被多次传递给比较函数时,结果应该彼此一致.也就是说,因为qsort它们应该在数组上定义总排序,并且对于bsearch同一个对象应始终以相同的方式与密钥进行比较.

(C99,§7.20.54,重点补充)

最后,正如Daniel Langr已经概述的那样,即使采用"原谅"的实施方式,这也不一定能达到你所追求的目标.

这就是说:抛弃这个kludge并使用一个真正稳定的排序算法,库已经提供它(std::stable_sort).

此外,由于这件事的整点似乎是比一个更快的排序std::stable_sort,并std::sort因qsort避免赋值操作符:

BTW qsort通常比std::sort廉价的比较器慢,因为它需要间接调用每个比较,而在std::sortfunctor内联.并且复制通常也较慢,因为std::sort必须使用memcpy(必须调用然后在运行时确定大小并相应地复制),同时内联赋值内联(所以再次,如果你的元素很小,它会更便宜,并且几乎相同,因为简单可分配类型的合成赋值/副本通常归结为memcpy

(聊天链接)

Answer 2

如果qsort从不调用compare(p,p),这将有效.

不,这不能确保快速排序的稳定性.如果这样做会很好:)

考虑相对于枢轴5划分(8,8,1,1).首先,外部8与外部1交换,然后内部8与内部1交换.分区后,1和8的顺序都会改变,而不是已经比较了具有相同键的元素.

它可以更明确地写成如下:

partition(8_left, 8_right, 1_left, 1_right) -> (1_right, 1_left, 8_right, 8_left)