l排序 排序是数据处理中经常使用的一种重要运算,如何进行排序,特别是如何进行高效的排 序,是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件,而记录则是由若 干数据项组成,其中的一项可用来标志一个记录,称为关键字项,该数据项的值称为关键字。 所谓排序,就是要整理文件中的记录,使得它按关键字递增(或递减)的次序排列起来。若 给定的文件含有n个记录{R,R Rn},它们的关键字分别为{K 要把这n个记录重新排列成为{R1,R2,…,Rn},使得{K1≥Ka≥…≥Km)(或{K1≤ K2≤…≤Kin})。 本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。 11枚举排序 111枚举排序及其串行算法 枚举排序( Enumeration sort)是一种最简单的排序算法,通常也称为秩排序( Rank sort)。 该算法的具体思想是(假设按关键字递增排序),对每一个待排序的元素统计小于它的所有 元素的个数,从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…an 中。首先将a[1与a[2]…an比较,记录比其小的数的个数,令其为k,a[]就被存入有序的 数组b[]…b[m的b[k+]位置上:然后将a[2]与a(1],a[3…am比较,记录比其小的数的个 数,依此类推。这样的比较操作共n(n-1)次,所以串行秩排序的时间复杂度为O(n2)。 算法13.1枚举排序串行算法 输入:a[]…an 输出:b[l…bn Be for i=l to n do (2)for j=l to n do ifa[i≥a[ 1 then (3)b[k}=a[ end for End 112枚举排序的并行算法 对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序, 只需是每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程 中,由主进程负责完成所有元素的最终排位。该并行算法描述如下 算法13.2枚举排序并行算法
1 1. 1 排序 排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排 序，是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若 干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。 所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。若 给定的文件含有 n 个记录｛R1，R2，…，Rn｝，它们的关键字分别为｛K1，K2，…，Kn｝， 要把这 n 个记录重新排列成为｛Ri1，Ri2，…，Rin｝，使得｛Ki1≥Ki2≥…≥Kin｝（或｛Ki1≤ Ki2≤…≤Kin｝）。 本章主要介绍了枚举排序、快速排序、PSRS 排序算法以及它们的 MPI 编程实现。 1.1 枚举排序 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（n 2）。 算法 13.1 枚举排序串行算法 输入：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.1.2 枚举排序的并行算法 对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序， 只需是每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程 中，由主进程负责完成所有元素的最终排位。该并行算法描述如下： 算法 13.2 枚举排序并行算法
输入:无序数组a[]…an] 输出:有序数组b[]…bn Begin 1)P播送a[]…an给所有 (2) for all Pi where I≤i≤ n para-do (2.1)k=1 (2.2)forj=I to n do if(a[i]>aDor(a0=a[] and i>j then k=k+1 end if end for (3)P收集k并按序定位 在该并行算法中,使用了n个处理器,由于每个处理器定位一个元素,所以步骤(2)的时 间复杂度为O(n):步骤(3)中主进程完成的数组元素重定位操作的时间复杂度为O(n),通 信复杂度分别为O(n):同时(1)中的通信复杂度为O(n2):所以总的计算复杂度为O(n) 总的通信复杂度为O(n2)。 MPI源程序请参见所附光盘。 12快速排序 121快速排序及其串行算法 快速排序( 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[1n 输出:有序数组data1n call procedure quicksort( data, I, n) procedure quicksort(data, i,j) Begin (1)ifi<))then (1. I)r= partition( data, i,j) (1.2)quicksort(data, i, r-1) (1.3)quicksort(data, r+1, j) end if End
2 输入：无序数组 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] and i>j) then k = k+1 end if end for (3) P0 收集 k 并按序定位 End 在该并行算法中，使用了 n 个处理器，由于每个处理器定位一个元素，所以步骤⑵的时 间复杂度为 O（n）；步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为 O（n），通 信复杂度分别为 O（n）；同时⑴中的通信复杂度为 O（n 2）；所以总的计算复杂度为 O（n）， 总的通信复杂度为 O（n 2）。 MPI 源程序请参见所附光盘。 1.2 快速排序 1.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 quicksort(data,1,n) End procedure quicksort(data,i,j) Begin (1) if (i<j) then (1.1)r = partition(data,i,j) (1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j); end if End
procedure partition(data, k, 7) Begin (3)for j=k to l-1 do if data[l]≤ pivo then =1+1 exchange data[i] and data[jl end if (4) exchange data[i+ 1] and data(/ (5)return i+l 快速排序算法的性能主要决定于输入数组的划分是否均衡,而这与基准元素的选择密切 相关。在最坏的情况下,划分的结果是一边有n-1个元素,而另一边有0个元素(除去被选 中的基准元素)。如果每次递归排序中的划分都产生这种极度的不平衡,那么整个算法的复 杂度将是e(n2)。在最好的情况下,每次划分都使得输入数组平均分为两半,那么算法的 复杂度为O( nlogn)。在一般的情况下该算法仍能保持O( nlogn)的复杂度,只不过其具有 更高的常数因子。 122快速排序的并行算法 快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两 个处理器完成递归排序。例如对一个长为n的序列,首先划分得到两个长为n2的序列,将 其交给两个处理器分别处理;而后进一步划分得到四个长为n4的序列,再分别交给四个处 理器处理;如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况,如果划 分步骤不能达到平均分配的目的,那么排序的效率会相对较差。算法13.4中描述了使用2m 个处理器完成对n个输入数据排序的并行算法 算法13.4快速排序并行算法 输入:无序数组data[1n],使用的处理器个数2m 输出:有序数组data[1n Begin para quicksort(data, 1, n, m, O) End procedure para quicksort(data, i, j, m, id) Begin l)if(-i)≤korm=0 (1. 1)Pid call quicksort( data, i, j) (1.2)Pud:P→p (1.3)Pid send data[r+1, m-1]to Pid+ m- (1. 4)para quicksort( data, i, r -1, m-1, id) (1.5)para quicksort(data, r+1, j, m-1, id-+2m-)
3 procedure partition(data,k,l) Begin (1) pivo=data[l] (2) i=k-1 (3) for j=k to l-1 do if data[j]≤pivo then i=i+1 exchange data[i] and data[j] end if end for (4) exchange data[i+1] and data[l] (5) return i+1 End 快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切 相关。在最坏的情况下，划分的结果是一边有 n-1 个元素，而另一边有 0 个元素（除去被选 中的基准元素）。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复 杂度将是Θ（n 2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的 复杂度为 O（nlogn）。在一般的情况下该算法仍能保持 O（nlogn）的复杂度，只不过其具有 更高的常数因子。 1.2.2 快速排序的并行算法 快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两 个处理器完成递归排序。例如对一个长为 n 的序列，首先划分得到两个长为 n/2 的序列，将 其交给两个处理器分别处理；而后进一步划分得到四个长为 n/4 的序列，再分别交给四个处 理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划 分步骤不能达到平均分配的目的，那么排序的效率会相对较差。算法 13.4 中描述了使用 2 m 个处理器完成对 n 个输入数据排序的并行算法。 算法 13.4 快速排序并行算法 输入：无序数组 data[1,n]，使用的处理器个数 2 m 输出：有序数组 data[1,n] Begin para_quicksort(data,1,n,m,0) End procedure para_quicksort(data,i,j,m,id) Begin (1) if (j-i)≤k or m=0 then (1.1)Pid call quicksort(data,i,j) else (1.2)Pid: r=patrition(data,i,j) (1.3)P id send data[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- send data(r+1, m-1] back to Pid end if 在最优的情况下该并行算法形成一个高度为logn的排序树,其计算复杂度为O(n), 通信复杂度也为O(n)。同串行算法一样,在最坏情况下其计算复杂度降为O(n2)。正常 情况下该算法的计算复杂度也为O(n),只不过具有更高的常数因子 MPI源程序请参见所附光盘 13PsRS排序 131PSRS算法原理 并行正则采样排序,简称PSRS( Parallel Sorting by Regular Sampling)它是一种基 于均匀划分( Uniform Partition)原理的负载均衡的并行排序算法。假定待排序的元素有 n个,系统中有p个处理器,那么系统首先将n个元素均匀地分割成p段,每段含有n/p个 元素,每段指派一个处理器,然后各个处理器同时施行局部排序。为了使各段中诸局部有序 的元素在整个序列中也能占据正确的位置,那么就首先从各段中抽取几个代表元素,再从他 们产生出p-1个主元,然后按这些主元与原各局部有序中的元素之间的偏序关系,将各个局 部有序段划分成p段,接着通过全局交换将各个段中的对应部分集合在一起,最后将这些集 合在一起的各部分采用多路归并的方法进行排序,这些有序段汇合起来就自然成为全局有序 序列了。 132PSRs算法形式化描述 设有n个数据,P个处理器,以及均匀分布在P个处理器上的n个数据。则PSRS算法 可描述如下: 算法135PsRS排序算法 输入:n个待排序的数据,均匀地分布在P个处理器上 输出:分布在各个处理器上,得到全局有序的数据序列 Begin 1)每个处理器将自己的n/P个数据用串行快速排序( Quicksort),得到一个排好序的 序列 (2)每个处理器从排好序的序列中选取第W,2w,3w,…,(P-1)w个共P-1个数据作为 代表元素,其中w=n/P2; (3)每个处理器将选好的代表元素送到处理器P。中,并将送来的P段有序的数据序列 做P路归并,再选择排序后的第P-1,2(P-1),…,(P-1)(P-1)个共P-1个主元; (4)处理器P将这P-1个主元播送到所有处理器中 (5)每个处理器根据上步送来的P-1个主元把自己的n/P个数据分成P段,记w!为处 理器P的第j1段,其中i=0,…,P-1,j=0, (6)每个处理器送它的第i+1段给处理器P,从而使得第i个处理器含有所有处理器的 第i段数据(i=0,…,P-1) (7)每个处理器再通过P路归并排序将上一步的到的数据排序:从而这n个数据便是有 End
4 (1.6)Pid+2m-1 send data[r+1,m-1] back to Pid end if End 在最优的情况下该并行算法形成一个高度为 logn 的排序树，其计算复杂度为 O（n）， 通信复杂度也为 O（n）。同串行算法一样，在最坏情况下其计算复杂度降为 O（n 2）。正常 情况下该算法的计算复杂度也为 O（n），只不过具有更高的常数因子。 MPI 源程序请参见所附光盘。 1.3 PSRS 排序 1.3.1 PSRS 算法原理 并行正则采样排序，简称 PSRS(Parallel Sorting by Regular Sampling)它是一种基 于均匀划分（Uniform Partition）原理的负载均衡的并行排序算法。假定待排序的元素有 n 个，系统中有 p 个处理器，那么系统首先将 n 个元素均匀地分割成 p 段，每段含有 n/p 个 元素，每段指派一个处理器，然后各个处理器同时施行局部排序。为了使各段中诸局部有序 的元素在整个序列中也能占据正确的位置，那么就首先从各段中抽取几个代表元素，再从他 们产生出 p-1 个主元，然后按这些主元与原各局部有序中的元素之间的偏序关系，将各个局 部有序段划分成 p 段，接着通过全局交换将各个段中的对应部分集合在一起，最后将这些集 合在一起的各部分采用多路归并的方法进行排序，这些有序段汇合起来就自然成为全局有序 序列了。 1.3.2 PSRS 算法形式化描述 设有 n 个数据，P 个处理器，以及均匀分布在 P 个处理器上的 n 个数据。 则 PSRS 算法 可描述如下： 算法 13.5 PSRS 排序算法 输入：n 个待排序的数据，均匀地分布在 P 个处理器上 输出：分布在各个处理器上，得到全局有序的数据序列 Begin (1) 每个处理器将自己的 n/P 个数据用串行快速排序(Quicksort)，得到一个排好序的 序列； (2) 每个处理器从排好序的序列中选取第 w，2w，3w，…，(P-1)w 个共 P-1 个数据作为 代表元素，其中 w=n/P2； (3) 每个处理器将选好的代表元素送到处理器 P0 中，并将送来的 P 段有序的数据序列 做 P 路归并，再选择排序后的第 P-1，2(P-1)，…，(P-1)(P-1)个共 P-1 个主元； (4) 处理器 P0 将这 P-1 个主元播送到所有处理器中； (5) 每个处理器根据上步送来的 P-1 个主元把自己的 n/P 个数据分成 P 段，记 j wi 为处 理器 Pi 的第 j+1 段，其中 i=0，…，P-1，j=0，…，P-1； (6) 每个处理器送它的第 i+1 段给处理器 Pi，从而使得第 i 个处理器含有所有处理器的 第 i 段数据(i=0，…，P-1)； (7) 每个处理器再通过 P 路归并排序将上一步的到的数据排序；从而这 n 个数据便是有 序的。 End
在该算法中,针对其中的计算部分(1)中的快速排序的代价为O( klogk),其中k=n/p; 第(2)步中各个处理器选择P个主元的代价为0(P);(3中对P个主元进行归并并选取新的主 元所需代价为0(F+1ogP;(5中对数据划分的代价为O(Pm/):最后第()步中各个处理 器进行并行归并的代价为0(m+1ogP)。针对通信部分(3)中处理器P收集P2个主元的代价 为O(門);(4)中播送新选择的P个主元的代价为0(P);最后第(6)步的多对多播送的通信 复杂度与具体的算法实现相关,其最大不会超过O(n)。 MPI源程序请参见章末附录 14小结 本章主要讨论了几个典型的并行排序算法,关于枚举匹配算法的具体讨论可参考[1]: 快速排序算法可以参考文献[2]和[3]中的介绍:文献[4]和[5]讨论了FSRS排序算 参考文献 [1]. Chabbar E, Controle, gestion du parallelisme: tris synchrones et asynchrones. Thesis de franch [2]. Lorin H Sorting and sort systems. Don Mills, Ontario: Addison-Wesley, 1975, 347-365 [3].陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,2002.11 [4]. Shi H, Schaeffer J Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14(4), 1992 5]. LiX, Lu P, Schaeffer J, Shillington J, Wong PS, Shi H On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, 1993 附录PSRS算法MP源程序 1.源程序 psrs_ sortc #include <stdio h> long dataSize. #include <stdlib.h> #include <mpi.h> int mylength; #define INIt TYPe 10 int*templ; #define ALLtooNE type 1 #define ONETOALL TYPe 200 main( int arge, char'argv) #define MUlti TYPe 300 #define RESULt TYPE 400 long BaseNum=1; #define result len 500 #define multi len 600
5 在该算法中，针对其中的计算部分⑴中的快速排序的代价为 O（klogk），其中 k=n/p； 第⑵步中各个处理器选择 P 个主元的代价为 O（P）；⑶中对 P 2 个主元进行归并并选取新的主 元所需代价为 O（P 2 +logP）；⑸中对数据划分的代价为 O（P+n/p）；最后第⑺步中各个处理 器进行并行归并的代价为 O（n/p+logP）。针对通信部分⑶中处理器 P0 收集 P 2 个主元的代价 为 O（P 2 ）；(4)中播送新选择的 P 个主元的代价为 O（P）；最后第(6)步的多对多播送的通信 复杂度与具体的算法实现相关，其最大不会超过 O（n）。 MPI 源程序请参见章末附录。 1.4 小结 本章主要讨论了几个典型的并行排序算法，关于枚举匹配算法的具体讨论可参考［1］； 快速排序算法可以参考文献［2］和［3］中的介绍；文献［4］和［5］讨论了 PSRS 排序算 法。 参考文献 [1]. Chabbar E, Controle, gestion du parallelisme: tris synchrones et asynchrones. Thesis Universite de Franche-comte, France:1980 [2]. Lorin H. Sorting and sort systems. Don Mills, Ontario: Addison-Wesley, 1975, 347~365 [3]. 陈国良 编著. 并行算法的设计与分析（修订版）. 高等教育出版社, 2002.11 [4]. Shi H, Schaeffer J. Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14(4), 1992 [5]. Li X, Lu P, Schaeffer J, Shillington J, Wong P S, Shi H. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, 1993 附录 PSRS 算法 MPI 源程序 1. 源程序 psrs_sort.c #include <stdio.h> #include <stdlib.h> #include <mpi.h> #define INIT_TYPE 10 #define ALLTOONE_TYPE 100 #define ONETOALL_TYPE 200 #define MULTI_TYPE 300 #define RESULT_TYPE 400 #define RESULT_LEN 500 #define MULTI_LEN 600 int Spt; long DataSize; int *arr,*arr1; int mylength; int *index; int *temp1; main(int argc,char* argv[]) { long BaseNum = 1; int PlusNum; int MyID; MPI_Init(&argc,&argv);