沈 阳 理 工 大 学
研 究 生 课 程 考 试 卷
壁纸少女
绿色的英语
课程名称： 并行程序设计
姓 名： 万晓东
专 业： 计算机系统结构
年 级： 2011
考 大数据分析软件号： 2011193 手机网络加速
授课或主讲教师签字：
多种排序的串行算法与并行算法的比较
摘 要
排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若给定的文件含有n个记录｛R1，R2，…，Rn｝，它们的关键字分别为｛K1，K2，…，Kn｝，要把这n个记录重新排列成为｛Ri1，Ri2，…，Rin｝，使得｛Ki1≥Ki2≥…≥Kin｝（或Ki1≤Ki2≤…≤Kin｝）。
本文主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。
关键词： 枚举排序、快速排序、PSRS排序算法MPI编程
Multiple sort of parallel algorithm with the rial algorithm
Abstract
Sorting is data processing often u a kind of important operation, and how to implement the sorting, especially how to carry on the effective sorting, is an important issue in computer application. Sort of object is a t of general records of documents, and records is compod by veral data item, one of the can be ud to mark a record, known as the key word items, this item of data value is called the key word.
The so-called sorting, is to be organizing the document records, make it according to the key words increa (or decrea) of quence up. If a given file contains n record {R1, R2,... , Rn}, their key words were {K1, K2,... , Kn}, will give this n record rearrange become {Ri1, Ri2,... , Rin}, make {Ki1 Ki2 Kin} quartile (or {than Ki2 than Kin}).
This paper品牌组合 introduces the enumeration, sort and quick sort, PSRS sort algorithm and their programming realize MPI.
Key words：enumeration, sort and quick sort, PSRS sort algorithm and realize MPI.
并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远
远不及串行算法那样丰富。并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。在以下的排序算法中，详细的比较了两种算法。
1.枚举排序
1.1枚举排序及其串行算法
枚举排序（Enumeration Sort）是一种最简单的排序算法，通常也称为秩排序（Rank Sort）。该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较，记录比其小的数的个数，令其为k，a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]，a[3]…a[n]比较，记录比其小的数的个数，依此类推。这样的比较操作共n(n-1)次，所以串行秩排序的时间复杂度为O（n2）。
枚举排序串行算法
输入：a[1]…a[n]
输出：b[1]…b[n]
Begin
For i=1 to n do
(1)k=1
(2)for j=1 to n do
if a[i]>a[j] then
k=k+1
End if
end for
(3)b[k]= a[i]
end for
End
1.2枚举排序的并行算法
对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。该并行算法描述如下：
输入：无序数组a[1]…a[n]
输出：有序数组b[1]…b[n]
Begin
( 1)P0播送a[1]…a[n]给所有Pi
(2)for all Pi where 1≤i≤n para-do
(2.1)k=1
(2.2)for j= 1 to n do
if (a[i] > a[j]) or(a[i] =a[j] andi>j) then
k = k+1
end if
end for
(3)P0收集k并按序定位
End
在该并行算法中，使用了n个处理器，由于每个处理器定位一个元素，所以步骤⑵的时间复杂度为O（n）；步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为O（n）；同时⑴中的通信复杂度为O（n2）；所以总的计算复杂度为O（n），总的通信复杂度为O（n2）。
2. 快速排序
2.1快速排序及其串行算法
快速排序（Quick Sort）是一种最基本的排序算法，它的基本思想是：在当前无序区R[1，n]中取一个记录作为比较的“基准”（一般取第一个、最后一个或中间位置的元素），用此基准将当前的无序区R[1，n]划分成左右两个无序的子区R[1，蔡艺林i-1]和R[i，n](1≤i≤n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字；当R[1，i-1]和R[i，n]非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止。
算法13.3 单处理机上快速排序算法
输入：无序数组data[1,n]
输出：有序数组data[1,n]
Begin
call procedure quick sort(data,1,n)
End
procedure quicksort(data,i,j)
Begin
(1)if (i<j) then
(1.1)r = partition(data,i,j)
(1.2)quick sort(data,i,r-1);
(1.3)quick sort(data,r+1,j);
end if
End
2.2快速排序的并行算法
快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。算法13.4中描述了使用2m个处理器完成对n个输入数据排序的并行算法。
快速排序并行算法：
输入：无序数组data[1,n]，使用的处理器个数2m
输出：有序数组data[1,n]
Begin
para_quick sort(data,1,n,m,0)
End
procedure para_quick sort(data,i,j,m,id)
Begin
(1)if (j-i)师生乱≤k or m=0 then
(1.1)Pidcall quick sort(data,i,j)
el
(1.2)Pid:：r=patrition(data,i,j)
(1.3)Pidnddata[r+1,m-1] to Pid+2m-1
(1.4)para_quicksort(data,i,r-1,m-1,id)
(1.5)para_quicksort(data,r+1,j,m-1,id+2m-1)
(1.6)Pid+2m-1nddata[r+1,m-1] back to Pid
end if
End
在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O（柴窑n），通信复杂度也为O（n）。同串行算法一样，在最坏情况下其计算复杂度降为O（n2）。正常情况下该算法的计算复杂度也为O（n），只不过具有更高的常数因子。
3.PSRS排序
3.1PSRS算法原理
并行正则采样排序，简称PSRS(Parallel Sorting by Regular Sampling)它是一种基于均匀划分（Uniform Partition）原理的负载均衡的并行排序算法。假定待排序的元素有n个，系统中有p个处理器，那么系统首先将n个元素均匀地分割成p段，每段含有n/p个元素，每段指派一个处理器，然后各个处理器同时施行局部排序。为了使各段中诸局部有序的元素在整个序列中也能占据正确的位置，那么就首先从各段中抽取几个代表元素，再从他们产生出p-1个主元，然后按这些主元与原各局部有序中的元素之间的偏序关系，将各个局部有序段划分成p段，接着通过全局交换将各个段中的对应部分集合在一起，最后将这些集合在
一起的各部分采用多路归并的方法进行排序，这些有序段汇合起来就自然成为全局有序列了。
3.2PSRS算法形式化描述
设有n个数据，P个处理器，以及均匀分布在P个处理器上的n个数据。则PSRS算法可描述如下：
PSRS排序算法
输入：n个待排序的数据，均匀地分布在P个处理器上
输出：分布在各个处理器上，得到全局有序的数据序列
Begin
(1)每个处理器将自己的n/P个数据用串行快速排序(Quick sort)，得到一个排好序的
序列；
(2)每个处理器从排好序的序列中选取第w，2w，3w，…，(P-1)w个共P-1个数据作为
