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

我正在寻找非递归奇偶合并排序算法,并找到了两个来源:

  • 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); } int main(char* argv, int args) { const int COUNT = 8; sort(0, COUNT); } 

结果:

 0 -o--------o-------------------------o---------------o------------------------- | | | | 1 -o--------|-o------o----------------|-o-------------oo----------------------- | | | | | | 2 -oo------o-|------oo--------------|-|-o----o--------oo--------------------- | | | | | | | | | 3 -oo--------o--------o--------------|-|-|-o--|-o--------oo-------o----------- | | | | | | | | 4 -ooo----o---o----o-----o----------o-|-|-|--o-|-o--------oo-----oo--------- | | | | | | | | | | | | | | 5 -ooo----|-o-|-o--oo---oo---o------o-|-|----o-|-o--------oo-----oo---o--- | | | | | | | | | | | | | | 6 -oooo--o-|-o-|----oo---oooo------o-|------o-|----------oo-----oooo- | | | | | | | | | | | | | | 7 -oooo----o---o------o-----o---o--------o--------o------------o-------o---o- 

当我知道正确的交换对并且算法等于图像时,我会将其转换为VHDL以便在我的硬件平台上进行测试。

其他开源硬件排序网络实现:

  • PoC.sort.sortnet.oddevensort
  • PoC.sort.sortnet.bitonicsort

附录:
Odd-even mergesort(又名Batcher的排序)就像是bitonic排序(不要与Batcher的bitonic排序混淆)。 但在硬件方面,这种算法的尺寸复杂度要高于bitonic排序,而延迟则相同。

与快速排序等快速软件算法相比,这些算法可以在良好的资源使用情况下实现。

维基百科: 奇偶合并

注意:
由于排序网络是静态的并且与输入值无关,因此不需要比较和交换来生成网络。 这就是它可以转化为硬件的一个原因。 我的代码生成比较操作的索引。 在硬件中,这些垂直连接将被比较和交换电路取代。 因此,未排序的数据将通过网络传输,并且在输出端将对其进行排序。

以下代码适用于任何大小的数组,不是递归的。 它是Perl的Algorithm::Networksort模块中相应函数实现的直接端口。 该实现恰好对应于Knuth在The Computer of Computer Programming,第3卷 (算法5.2.2M)中描述的算法。 实际修复你的算法没有帮助,但它至少给你一个有效的非递归实现Batcher的奇偶合并,只有三个嵌套循环:)

 #include  #include  void oddeven_merge_sort(int length) { int t = ceil(log2(length)); int p = pow(2, t - 1); while (p > 0) { int q = pow(2, t - 1); int r = 0; int d = p; while (d > 0) { for (int i = 0 ; i < length - d ; ++i) { if ((i & p) == r) { printf("%2i cmp %2i\n", i, i + d); } } d = q - p; q /= 2; r = p; } p /= 2; } } 

如果您可以获得“计算机编程艺术”第3卷的副本,您将对算法的工作原理和原因以及一些其他细节有一个很好的解释。

我想我找到了解决方案。 我检查了它的length = 2, 4, 8, 16

这是我的代码:

 void sort(int length) { int G = log2ceil(length); // number of groups for (int g = 0; g < G; g++) // iterate groups { int B = 1 << (G - g - 1); // number of blocks for (int b = 0; b < B; b++) // iterate blocks in a group { for (int s = 0; s <= g; s++) // iterate stages in a block { int d = 1 << (g - s); // compare distance int J = (s == 0) ? 0 : d; // starting point for (int j = J; j+d < (2< 

该解决方案引入了第五个for循环来处理组中的子块。 j循环具有更改的开始和中止值,以处理后合并步骤的奇数计数而不生成加倍的比较步骤。

这是一个固定的非递归子程序。

 void sort(int n) { 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++) // wrong for (int i = 0; i < k; i++) // correct if ((i + j)/(p + p) == (i + j + k)/(p + p)) printf("%2i cmp %2i\n", i + j, i + j + k); } 

要么

 void sort(int n) { for (int p = 1; p < n; p += p) for (int k = p; k > 0; k /= 2) for (int j = 0; j < k; j++) for (int i = k % p; i + k < n; i += k + k) if ((i + j)/(p + p) == (i + j + k)/(p + p)) printf("%2i cmp %2i\n", i + j, i + j + k); }