Tag: 排序网络

如何修复这种非递归奇偶合并排序算法？

我正在寻找非递归奇偶合并排序算法，并找到了两个来源： Sedgewick R.的一本书 这个问题 两种算法都相同但是错误。 生成的排序网络不是奇偶合并排序网络。 以下是具有32个输入的结果网络的图像。 2条水平线之间的垂直线表示将值a [x]与[y]进行比较，如果大于，则交换数组中的值。 32个输入的奇偶合并排序http://sofzh.miximages.com/c/11fig07.gif （可点击） 我将代码从Java复制到C并用printf替换了exch函数来打印交换候选者。 当绘制对的图时，可以看出生成了太多对。 有谁知道如何修复此算法？ 为什么我需要非递归版本？ 我想将这个排序网络转换为硬件。 将管道阶段插入非递归算法很容易。 我还调查了递归版本，但是将算法转换为流水线硬件太复杂了。 我的C代码： #include #include void sort(int l, int r) { int n = r-l+1; for (int p=1; p0; k/=2) for (int j=k%p; j+k<n; j+=(k+k)) for (int i=0; i<njk; i++) if ((j+i)/(p+p) == (j+i+k)/(p+p)) printf("%2i cmp %2i\n", l+j+i, l+j+i+k); […]

标准排序网络，用于n的小值

我正在寻找一个5元素排序的排序网络实现，但由于我在SO上找不到好的参考，我想要求为所有小的n值排序网络，至少n = 3通过n = 6但更高的值也会很大。 一个好的答案至少应该将它们列为“交换”（在2个元素上排序）操作的序列，但是在低阶排序网络方面看到递归分解也可能会很好。 对于我的应用程序，我实际上只关心5个元素的中位数，而不是实际按顺序排列。 也就是说，只要中位数在正确的位置结束，结果中可能未指定其他4个元素的顺序。 可以使用与排序网络相关的方法来计算交换数量少于执行完整排序的中位数吗？ 如果是这样，我的问题（对于n = 5）和其他情况的这种解决方案也会得到一个很好的答案。 （注意：我已经标记了这个问题C，因为C是我使用的语言，我怀疑跟随C标签的人有很好的答案，但我真的不在乎答案实际上是用C语言编写而不是伪代码只要符合上述标准，它就可以很容易地转换为C语言。）