1

我正在通过此处描述的常规采样算法实现并行排序。我陷入了需要将已排序的子列表迁移到已排序数组的适当位置的地步。问题可以这样说：有一个全局数组。该数组已被划分为 p 个子数组。这些子数组中的每一个都已排序。p-1 个全局枢轴元素被确定，每个子数组被分成 p 个子子数组（黄色、红色、绿色）。现在我需要移动这些子子数组，以便具有局部索引 i 的子子数组位于线程 i 中（因此它们以颜色相邻且从左到右的顺序保持不变的方式排序）。

实际上串行算法会做，但我只是不知道如何获得适当的排列。下图显示了 p=3 个线程的情况。黄色表示子子数组 0，红色 - 1，绿色 - 2。

问题可视化

子子阵列可以具有不同的大小。

4

1 回答 1

0

好的似乎我没有足够的声誉来评论您的问题，所以我将采取发布答案的方式。

所以让我直截了当。你被困在这个算法的第 3 阶段。正确的？

这个怎么样：

让我们有 p 个索引的链接列表。让每个进程将索引范围传递给进程 i；随着索引的传递，将索引附加到进程 i 的列表中。当所有的通信都结束时，你应该在进程 i 的列表中拥有进程 i 的所有索引。此列表的节点应该是一个数据结构，如

 Node {
      index
      valueOfIndex
 }

现在，当您填充列表时，将其值也复制到列表中。

一旦你完成了这个过程。您可以使用列表 i 为进程 i 重新创建数组。

？？？

于 2013-07-11T07:17:25.833 回答