并行排序
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此条目没有列出任何参考或来源。 (2020年4月29日) |
并行排序算法是电脑并行计算能力大大发展之后,为了提高排序效率而提出的算法。
划分的设计方法
- PSRS算法
- Viliant归并算法
- 对数划分
串行算法直接并行化
- 模拟快速排序
- 二叉树上模拟快速排序
- 串行算法简介:快速排序是一种较为高效的排序算法,它通过不断的划分待排序列为两段,使得前一段总小于或等于某个数,而后一段总大于某个数,这样每次划分就能确定一个数的最终位置。一般情况下,如果每次划分的两个子列大致等长,那么它的时间复杂度是。
- 在PRAM-CRCW计算模型上利用二叉树网络模拟快速排序
- 由快速排序的过程,我们可以看到,快速排序实际上就是在构造一棵二叉树,让划分主元位于根节点,使得左子节点小于或等于根而右子节点大于根,最后对整棵二叉树进行一次中序遍历,便可以得到最后排好序的数列。
- 我们可以选n个处理器分别保存待排序数组A的n个元素,处理器对应一个变量用于存放主元元素的处理器号,以及两个变量L,R分别存放其左右儿子。开始时,每一个处理器都试图往变量root中写入它的处理器号,若果我们使用PRAM-CRCW计算模型,那么就只有一个能够写入root,接着root被复制给每一个处理器的。然后对于每个处理器(除去被原为主元的那个外)判断其值与的大小,从而确定放入还是,同样的,由于并发操作的互斥性,只有一个只能被最终写入,他们就作为下次划分的主元。算法继续进行直到n个主元被选完为止。
- 时间复杂度分析:由于一层节点的构造时间是,所以算法的时间复杂度是
- 超立方体上模拟快速排序
- 超立方体网络是基于超立方体连接构建的网络。网络中以格雷码对各顶点编号。在下面的描述中,设顶点数,待排序元素共有n个。
- 超立方体上的快速排序是这样进行的:首先我们将n个元素分配到p个处理器上,为了使问题讨论简单化,假设n是p的整数倍,那么每个顶点将会分到个元素。然后随机选一个主元,各个处理器将每个顶点中的元素按与主元的比较结果分为两部分。这个算法的关键点在这里,对每一个处理器(顶点)在进行第i次划分时,将大于主元的部分都送到超立方体的一个d-i维自立方体中,而将小于主元的部分送到另一个d-i位的子立方体中,这样就模拟了快速排序中的划分算法。子立方体可以这样选择:在第i次划分中判断第i位是0还是1。划分算法到处理完所有1维子立方体后结束。接下来对每个顶点中的元素调用串行算法进行局部排序,最后对整个立方体进行一次遍历便可得到排好序的元素。
- 二叉树上模拟快速排序
比较器络上的并行排序网
比较器网络一般是指由Batcher比较器构成的网络。这些比较器均可以执行两个数之间的比较与条件交换(CCI)操作。Batcher归并网络可以由较小的Batcher归并网络递归地组成。Batcher排序网络可以分为奇偶排序网络(Odd-Even Sorting Network)和双调排序网络两大类。
参阅
|
|