排序网络 - 哪些网络允许跳过比较？

Question

GCC 的 qsort 实现使用 3 的中位数来选择主元。在此过程中，这 3 个元素通过排序网络进行排序。

3 个元素的排序网络通常需要 3 次比较。但在这个特定的实现中，可以跳过最后一次比较，具体取决于之前的比较:

if(a[0] > a[1]) swap(a[0], a[1]);
if(a[1] > a[2]) swap(a[1], a[2]);
else goto jump;
if(a[0] > a[1]) swap(a[0], a[1]);
jump:;

是否可以对 n = 4...16 的网络(具有已知的最小最佳比较次数的网络)执行类似的操作？如果是的话，是哪些以及它们会是什么样子？

更新:到目前为止，我已经找到了另一个网络，可以跳过一次比较:

// sorting network for 5 elements
if (a[0] > a[1]) { SWAP(a[0], a[1]); }
if (a[2] > a[3]) { SWAP(a[2], a[3]); }

if (a[1] > a[3]) { SWAP(a[1], a[3]); }
if (a[2] > a[4]) { SWAP(a[2], a[4]); }

if (a[0] > a[2]) { SWAP(a[0], a[2]); }
if (a[1] > a[4]) { SWAP(a[1], a[4]); }

if (a[1] > a[2]) { SWAP(a[1], a[2]); }
if (a[3] > a[4]) { SWAP(a[3], a[4]); }
else { goto jump; }

if (a[2] > a[3]) { SWAP(a[2], a[3]); }
jump:;

我用 12345 的所有排列对此进行了测试，并且它对所有排列都正确排序。

Answer 1

抛开最佳排序网络不谈，下图展示了一种通过使用大小为n的排序网络创建任意大小的排序网络n+1的方法，然后执行n 额外比较以将最后一个元素放置到位(这通常是插入排序在转换为排序网络后的工作方式):

该图像非常明显，如果元素 n+1 已经是最大的元素，那么您可以跳过比较元素 n 之后的每个比较器和n+1。基本上，一旦最后一个 n 个比较器返回 false，您就可以跳过以下比较器。从总体上看，我想说可以跳过大多数排序网络中的比较。

也就是说，一旦您的排序算法中有这样的条件，那么它就不再是排序网络，并且您将失去排序网络的好处:正确实现时不会出现分支预测问题。

如果您的目标只是通过尽可能少的比较和交换对小集合进行排序，那么您可以unroll every possible path排序算法，然后为每条路径执行最佳数量的移动/交换，但是这种方法在超过 4 个元素时变得完全无法维护，并且您的类型不太可能具有足够昂贵的移动和比较操作来证明这种算法的合理性。