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% 稳定的排序数组。这是 link：https://ideone.com/KOYbgJ

VC++Express 2008 编译器失败稳定排序，因为指针的顺序已更改。这基本上显示了 VC++ 实现与 GCC 实现的不同之处在于它不保持指针顺序。

Answer 1

任何未明确禁止的内容都是默认允许的；特别是，我记得调试构建中的 VC++ 在实际执行 std::sort 之前显式测试同一元素上的比较器（以及其他健全性测试）。不知道它是否与 qsort 一样，但它是允许的。

但最重要的是，您的比较器违反了 qsort 规定的要求；特别是：

When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key.

（C99，§7.20.5 ¶4，已强调）

最后，正如 Daniel Langr 所概述的那样，即使使用 "forgiving" 实现，这也不一定能实现您的目标。

就是说：扔掉这个笨拙的东西，使用真正稳定的排序算法，库已经提供了它(std::stable_sort)。

此外，由于 qsort 避免了赋值运算符，这件事的全部意义似乎是比 std::stable_sort 和 std::sort 更快的排序：

BTW qsort is generally slower than std::sort for cheap comparers because it requires an indirect call for each compare, while in std::sort the functor gets inlined. and copying is often slower as well, as std::sort has to use memcpy (which has to be called and then to determine at runtime the size and copy accordingly), while an inlined assignment gets inlined (so again, it's way cheaper if your elements are small, and pretty much the same otherwise, as the synthesized assignment/copy of trivially assignable types generally boils down to memcpy

(chat link)

Answer 2

This will work if qsort never calls compare(p,p).

不，这不能保证快速排序的稳定性。如果能的话就好了:)

考虑对(8,8,1,1)进行分区，关于主元5。首先，外层8与外层1交换，然后内层8与内层1交换。1和8的顺序是分区后更改，但没有比较具有相同键的元素。

可以更明确地写成：

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

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

Does C++ qsort ever compare an element with itself?

c++

qsort