QuickSort Dijkstra 3-Way Partitioning:为什么要额外交换？

Question

根据这里的算法,看看我在"X"的情况,发生以下情况:

场景: i - >"X","X">"P"

1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

为什么我们不直接递减gt,直到gt指向<lt的值(在这种情况下为"P"),然后我们将此值与i处的值交换.这将节省交换操作.

因此,如果我们为上述场景做到这一点,我们将做:

1. gt--
2. gt--
3. swap("X", "C"), gt--;   
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

这种算法需要进行过多的交换吗？它以某种方式提高了性能吗？如果它确实提高了性能,怎么样？

如果它不影响性能,请提供正确的解释或证明为什么它不会影响性能.

另外,我提到的第二种方法会以任何方式影响性能吗？请解释原因.

上面使用的PS"影响性能"意味着改善/降低性能.

Answer 1

你是对的,额外的交换操作不是必需的,这里的算法最好是为了清晰,但不是为了性能.请参阅快速排序(3路分区)的讨论.

在Quicksort中,Robert Sedgewich本人是最佳的,他有一种不同的方法,使用更少的交换操作,但你可以想象它也需要更多的代码,并且不如演示中的算法清晰.

Answer 2

该算法基于Dijkstra对"荷兰国旗的问题"的解决方案,该解决方案出现在1976年出版的"编程学科"一书中(第111页).Dijkstra的目标是为多本推导出可证明的正确解决方案.问题.不只是展示最终结果,而是实际完成设计过程.

在"荷兰国旗问题"中,Dijkstra设想了一排水桶(思想阵列),每个水桶都包含一块红色,白色或蓝色(荷兰国旗的颜色)的鹅卵石.只有两个操作的迷你电脑.它可以交换两个桶的内容,它可以检查桶中的鹅卵石的颜色.他将后一种操作的使用限制在每个桶的单次检查中.后者就足够了,因此这就是他所选择的优雅简约风格.在证明正确性方面,尽可能少的情况下考虑绝对是一个优势.以下是他的一篇着作中的一句话:"......一旦发现自己面临必须区分大量案件的案例分析,就会变得非常可疑".

转换为排序问题,相当于最多N次比较.这实际上很常见.在C++标准中,不同排序算法和堆操作的复杂性是根据比较的数量.不是掉期数量.想法是交换是便宜的,如果不使用间接(指针)使其便宜.然而,比较可能很昂贵.因此,在比较次数方面说明复杂性更有意义.

是的,您可以减少掉期数量,但如果您想要最多进行N次比较则不会.