Tag: hdl

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

我正在寻找非递归奇偶合并排序算法，并找到了两个来源： 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); […]