多种排序的串行算法与并行算法的比较

1、沈阳理工大学研 究生课 程考试 卷评 分课程名称：并行程序设计姓名：万晓东专业：计算机系统结构年级：2011考号：2011193授课或主讲教师签字：多种排序的串行算法与并行算法的比较摘要排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排 序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若 干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。 所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若 给定的文件含有n个记录R1，R2，Rn，它们的关键字分别为K1，K2，Kn， 要把这n个

2、记录重新排列成为 %，Ri2，Rin，使得 K1 3Ki2 33Kin （或 、W Ki2 aj thenk=k+1End ifend forbk= aiend forEnd1.2枚举排序的并行算法对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序， 只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程 中，由主进程负责完成所有元素的最终排位。该并行算法描述如下： 输入：无序数组a1an 输出：有序数组b1bnBeginP(播送a1an给所有当for all Pi where 1 WiWn para-do(2.1)k=1(2.2)for j=

3、 1 to n doif (ai aj) or(ai =aj andij) thenk = k+1end ifend for(3)P0收集k并按序定位End在该并行算法中，使用了n个处理器，由于每个处理器定位一个元素，所以步骤的时 间复杂度为。(n)；步骤中主进程完成的数组元素重定位操作的时间复杂度为0(n)，通 信复杂度分别为。(n)；同时中的通信复杂度为。(n2)；所以总的计算复杂度为。(n)， 总的通信复杂度为。(n2)。快速排序2.1快速排序及其串行算法快速排序(Quicksort)是一种最基本的排序算法，它的基本思想是：在当前无序区R1， n中取一个记录作为比较的“基准”(一般取第一

4、个、最后一个或中间位置的元素)，用此 基准将当前的无序区R1，n划分成左右两个无序的子区R1，i-1和Ri，n(1WiWn)，且 左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所 有关键字均大于等于基准的关键字；当R1，i-1和Ri，n非空时，分别对它们重复上述的 划分过程，直到所有的无序子区中的记录均排好序为止。算法133单处理机上快速排序算法输入：无序数组data1,n输出：有序数组data1,nBegincall procedure quick sort(data,1,n)Endprocedure quicksort(dataJJ)Begin(1)if (

5、ij) thenr = partition(data,i,j)quick sort(data,i,r-1);quick sort(data,r+1,j);end ifEnd2.2快速排序的并行算法快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个 处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交 给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器 处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步 骤不能达到平均分配的目的，那么排序的效率会相对较差。算法13.4中描述了

6、使用2皿个处理 器完成对n个输入数据排序的并行算法。快速排序并行算法：输入：无序数组data1,n，使用的处理器个数2m输出：有序数组data1,nBeginpara_quick sort(data,1,n,m,0)Endprocedure para_quick sort(data,i,j,m,id)Begin(1)if (j-i)Wk or m=0 thenPid call quick sort(data,i,j)elsePid. r=patrition(data,i,j)Pidsenddatar+1,m-1 to Pid+2m-1para_quicksort(data,i,r-1,m-1,

7、id)para_quicksort(data,r+1,j,m-1,id+2m-1)Pid+2m-1 senddatar+1,m-1 back to Pidend ifEnd在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O (n)， 通信复杂度也为O (n)。同串行算法一样，在最坏情况下其计算复杂度降为O (n2)。正常 情况下该算法的计算复杂度也为O (n)，只不过具有更高的常数因子。3.PSRS排序3.1PSRS算法原理并行正则采样排序，简称PSRS(Parallel Sorting by Regular Sampling)它是一种基 于均匀划分(Uniform Pa

8、rtition)原理的负载均衡的并行排序算法。假定待排序的元素有 n个，系统中有p个处理器，那么系统首先将n个元素均匀地分割成p段，每段含有n/p个 元素，每段指派一个处理器，然后各个处理器同时施行局部排序。为了使各段中诸局部有序 的元素在整个序列中也能占据正确的位置，那么就首先从各段中抽取几个代表元素，再从他 们产生出p-1个主元，然后按这些主元与原各局部有序中的元素之间的偏序关系，将各个局 部有序段划分成p段，接着通过全局交换将各个段中的对应部分集合在一起，最后将这些集 合在一起的各部分采用多路归并的方法进行排序，这些有序段汇合起来就自然成为全局有序 列了。3.2PSRS算法形式化描述设有

9、n个数据，P个处理器，以及均匀分布在P个处理器上的n个数据。则PSRS算法可描述 如下：PSRS排序算法输入：n个待排序的数据，均匀地分布在P个处理器上输出：分布在各个处理器上，得到全局有序的数据序列Begin每个处理器将自己的n/P个数据用串行快速排序(Quick sort)，得到一个排好序的序列；每个处理器从排好序的序列中选取第w，2w，3w，(P-1)w个共P-1个数据作为代表元素，其中w=n/P2；每个处理器将选好的代表元素送到处理器P0中，并将送来的P段有序的数据序列做P路归并，再选择排序后的第P-1，2(P-1)，(P-1)(P-1)个共P-1个主元；处理器P0将这P-1个主元播送

10、到所有处理器中；每个处理器根据上步送来的P-1个主元把自己的n/P个数据分成P段，记为处j i w理器Pi的第j+1段，其中i=0，P-1，j=0，P-1；每个处理器送它的第i+1段给处理器Pi，从而使得第i个处理器含有所有处理器的第i段数据(i=o,，p-1)；. Chabbar E, Controle, gestion du parallelisme: tris synchrones et asynchrones. Thesis Universite de Franche-comte, France:1980 . Lorin H. Sorting and sort systems. Don

11、 Mills, Ontario: Addison-Wesley, 1975, 347365 .陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,2002.11 . Shi H, Schaeffer J. Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14(4), 1992 . Li X, Lu R Schaeffer J, Shillington J, Wong PS, Shi H. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, 1993每个处理器再通过P路归并排序将上一步的到的数据排序；从而这n个数据便是有序的END在该算法中，针对其中的计算部分中的快速排序的代价为O(klogk)，其中k=n/p；第 步中各个处理器选择P个主元的代价为O(P)；中对P2个主元进行归并并选取新的主元所 需代价为O(P2+logP)；中对数据划分的代价为O(P+n/p)；最后第步中各个处理器进 行并行归并的代价为O(n