我正在寻找非递归奇偶合并排序算法,并找到了两个来源:
-
来自Sedgewick R.的书
两种算法都相同但是错误 . 生成的排序网络不是奇偶合并排序网络 .
以下是具有32个输入的结果网络的图像 . 2条水平线之间的垂直线表示将值a [x]与[y]进行比较,如果大于,则交换数组中的值 .
odd-even-merge sort for 32 inputs http://flylib.com/books/3/55/1/html/2/images/11fig07.gif(可点击)
我将代码从Java复制到C并用 printf
替换了 exch
函数来打印交换候选者 .
当绘制对的图时,可以看出生成了太多对 .
Has anyone an idea how to fix this algorithm?
为什么我需要非递归版本?
我想将这个排序网络转换为硬件 . 将管道阶段插入非递归算法很容易 .
我还调查了递归版本,但是将算法转换为流水线硬件太复杂了 .
我的C代码:
#include <stdlib.h>
#include <stdio.h>
void sort(int l, int r)
{ int n = r-l+1;
for (int p=1; p<n; p+=p)
for (int k=p; k>0; k/=2)
for (int j=k%p; j+k<n; j+=(k+k))
for (int i=0; i<n-j-k; i++)
if ((j+i)/(p+p) == (j+i+k)/(p+p))
printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
sort(0, COUNT);
}
结果:
0 -o--------o-------------------------o---------------o-------------------------
| | | |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
| | | | | |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
| | | | | | | | |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
| | | | | | | |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
| | | | | | | | | | | | | |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
| | | | | | | | | | | | | |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
| | | | | | | | | | | | | |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-
当我知道正确的交换对并且算法等于图像时,我会将其转换为VHDL以便在我的硬件平台上进行测试 .
其他开源硬件排序网络实现:
Appendix:
Odd-even mergesort(a.k.a Batcher 's sort) is like bitonic sort (not to confuse with Batcher' s bitonic sort) . 但在硬件方面,这种算法的尺寸复杂度要高于bitonic排序,而延迟则相同 .
与快速排序等快速软件算法相比,这些算法可以在良好的资源使用情况下实现 .
维基百科:odd-even mergesort
Note:
由于排序网络是静态的并且与输入值无关,因此不需要比较和交换来生成网络 . 这就是它可以转化为硬件的一个原因 . 我的代码生成比较操作的索引 . 在硬件中,这些垂直连接将被比较和交换电路取代 . 因此,未排序的数据将通过网络传输,并且在输出端将对其进行排序 .
3 回答
以下代码适用于任何大小的数组,不是递归的 . 它是Perl的
Algorithm::Networksort
模块中the corresponding function实现的直接端口 . 该实现恰好对应于Knuth在The Computer of Computer Programming,第3卷(算法5.2.2M)中描述的算法 . 它没有't help to actually fix your algorithm, but it at least gives you a working non-recursive implementation of Batcher'奇数 - 偶数mergesort只有三个嵌套循环:)如果您可以获得“计算机编程艺术”第3卷的副本,您将对算法的工作原理和原因以及一些其他细节有一个很好的解释 .
我想我找到了解决方案 . 我查了一下
length = 2, 4, 8, 16
.这是我的代码:
该解决方案引入了第五个for循环来处理组中的子块 . j循环具有更改的开始和中止值,以处理后合并步骤的奇数计数,而不会生成加倍的比较步骤 .
这是一个固定的非递归子程序 .
要么