如何解决这个问题非递归奇偶合并排序算法？ [英] How to fix this non-recursive odd-even-merge sort algorithm?

问题描述

我正在寻找非递归奇偶合并排序算法，发现2来源：

I was searching for non-recursive odd-even-merge sort algorithm and found 2 sources:

• 一书从塞奇威克R.


• 此 SO质疑

• a book from Sedgewick R.
• this SO question

这两种算法是相同的，但假的。由此产生的排序网络不是奇偶合并排序网络。

Both algorithms are identical but false. The resulting sorting network is not an odd-even-merge sort network.

下面是与32个输入所得网络的图像。 2水平行之间的垂直线表示比较值的[X]与[y]的，如果大于交换数组中的值。

Here is an image of the resulting network with 32 inputs. A vertical line between 2 horizontal lines means compare value a[x] with a[y], if greater then swap the values in the array.

（点击）

我复制了code从Java到C和替换 EXCH 由的printf 打印功能交流人选。

I copied the code from Java to C and replaced the exch function by a printf to print the exchange candidates.

当一个绘制成对的图，可以看出，太多的对产生

When one draws a diagram of the pairs, it can be seen that too many pairs are generated.

有没有人一个想法如何解决这一问题的算法？

为什么需要非递归版本？结果
我想这个排序网络转化为硬件。这很容易流水线阶段插入到非递归算法。

Why do I need non-recursive version?
I want to transform this sorting network into hardware. It's easy to insert pipeline stages into a non-recursive algorithms.

我还调查了递归版本，但它太复杂的算法转换成流水线硬件。

I also investigated the recursive version, but it's too complex to transform the algorithm into pipelined hardware.

我的C code：

#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在我的硬件平台测试。

When I know the correct exchange pairs and the algorithm is equal to the image, I'll translate it into VHDL for tests on my hardware platform.

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

Other open source hardware sorting network implementations:

• PoC.sort.sortnet.oddevensort


• PoC.sort.sortnet.bitonicsort

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

附录：结果
奇偶归并（a.k.a配料的排序）就像是双调排序（不要与配料的双调排序混淆）。但在硬件算法具有比双调排序更好的尺寸复杂性，而延迟是一样的。

Appendix:
Odd-even mergesort (a.k.a Batcher's sort) is like bitonic sort (not to confuse with Batcher's bitonic sort). But in hardware this algorithm has a better size complexity than bitonic sort, while latency is the same.

这些算法可以有良好的资源使用来实现比较快的软件算法，如快速排序。

These algorithm can be implemented with good resource usage compared to fast software algorithms like quicksort.

百科：奇偶归并

注意：结果
因为排序网络是输入值的静态和独立的，没有比较和需要交换，以产生网络。这是原因之一，可以转化为硬件。我的code生成用于比较操作的指数。在硬件上，这些垂直的连接将通过比较和交换电路来代替。所以未排序的数据将前往throught网络并在输出侧将被排序。

Note:
Because sorting networks are static and independent of the input values, no compare and swap is needed to generate the network. That's one reason why it can be transformed into hardware. My code generates the indices for the compare operations. In hardware, these vertical connections will be replaced by compare and swap circuits. So unsorted data will travel throught the network and on the output side it will be sorted.

推荐答案

我想我找到了解决办法。我检查它长度= 2，4，8，16 。

I think I found a solution. I checked it for length = 2, 4, 8, 16.

下面是我的code：

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<<g); j += 2*d)  // iterate startpoints
        { for (int i = 0; i < d; i++)            // shift startpoints
          { int x = (b * (length / B)) + j + i;  // index 1
            int y = x + d;                       // index 2
            printf("%2i cmp %2i\n", x, y);
          }
        }
      }
   }
}

该解决方案引入了循环处理一组子块的五分之一。
j循环有一个改变的起始和终止值处理后的奇数合并步骤，而不会产生比较翻了一番步骤。

This solution introduces a fifth for-loop to handle subblocks in a group. The j loop has a changed start and abort value to handle odd counts of post merge steps without generating doubled compare steps.

这篇关于如何解决这个问题非递归奇偶合并排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！