哪种排序方法最适合并行处理？

Question

10

我现在正在查看我的旧校作业，想找到一个问题的解决方案。

哪种排序方法最适合并行处理？

我猜测快速排序（或者归并排序？）是答案。

我正确吗？

- Billy

6个回答

10

这完全取决于并行化方法。对于多线程通用计算，归并排序提供了相当可靠的负载平衡和内存本地化特性。对于硬件中的大型排序网络，如果您想要良好的O（log² n）性能，则最好使用Batcher、Bitonic或Shell排序。

- Sam Harwell

4

我认为归并排序

你可以将数据集分割并对它们进行并行操作。

- ufukgun

8

我的名字是Ufuk Gün，但用英语发音听起来很有趣 :) - ufukgun

2

归并排序需要线程之间的同步来合并排序结果。快速排序不需要任何线程同步。 - Ben S

1

我认为归并排序是最好的答案。因为归并排序的基本思想是将问题分解为单独的解决方案。解决它们，然后合并它们。

这也是我们在并行处理中实际上所做的。将整个问题分解为小的单元语句以并行计算，然后合并结果。谢谢。

- mojito89

1

这里有几点随机的评论：

许多有关如何轻松并行化快速排序的讨论都忽略了枢轴选择。如果你遍历数组来查找它，就会引入一个线性时间的顺序组件。
在分布式内存中实现快速排序并不容易。Kumar书中有一些讨论。
是的，我知道，不应该使用冒泡排序。但是，“奇偶换位排序”，它更或多或少等价，实际上是一个相当不错的并行编程练习。特别是对于分布式内存并行性。这是一个最简单的排序网络示例，在MPI等中非常可行。

- Victor Eijkhout

0

这是归并排序，因为排序是在两个子数组上完成的，并且它们在最后进行比较和排序。这些可以并行完成

- Nimmy

我认为没有必要重复现有的答案。 - Mysticial

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Irwin M. Fletcher · Accepted Answer

与归并排序类似，快速排序也因其分治的性质可以轻松地并行化。单独的原地分区操作很难并行化，但是一旦被分割，列表的不同部分可以并行排序。

与其他并行排序算法相比，并行快速排序的一个优点是不需要同步。一旦子列表可供新线程使用，它就会立即启动，并且它不会与其他线程通信。当所有线程完成时，排序就完成了。