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

Question

GCC实现的qsort使用中位数法来选择枢轴。在此过程中，这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排列组合，这个程序都能正确地排序。

- Miroslav Cetojevic

---

当你到达条件比较时，如果没有发生交换，那么最终的比较似乎是多余的。你可以通过使用第二个原始索引数组来跟踪已经比较过的元素，并将该数组与数据一起交换，以及一个大小为(n^2 - n) / 2的元素可能比较次数的数组（n个元素每次取两个），初始化为零并设置为每次比较时加一。 - rcgldr

Answer 1

不考虑最优排序网络，下面的图片展示了一种创建任意大小为n+1的排序网络的方法，即使用大小为n的排序网络，然后执行n个额外的比较来将最后一个元素放置在正确位置（这通常是将插入排序转换为排序网络的方式）：

如果元素n+1已经是最大的，那么图像很明显，你可以跳过比较元素n和n+1之后的每个比较器。基本上，一旦任何一个n个最后的比较器返回false，你就可以跳过以下的比较器。在整个排序网络中，我认为在大多数排序网络中都可以跳过比较。

话虽如此，一旦在您的排序算法中有这样的条件语句，它就不再是一个排序网络了，并且您失去了排序网络的好处：当正确实现时，不会出现分支预测问题。

如果您的目标只是对少量集合进行尽可能少的比较和交换排序，则可以展开排序算法的每个可能路径，然后对每个路径执行最优数量的移动/交换，但是这种方法在4个元素以上就变得难以维护，而且您的类型很可能没有足够昂贵的移动和比较操作来证明这样的算法是合理的。

- Morwenn