多種排序的串行算法與并行算法的比較

1、沈陽理工大學(xué)研 究生課 程考試 卷評(píng) 分課程名稱：并行程序設(shè)計(jì)姓名：萬曉東專業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)年級(jí)：2011考號(hào)：2011193授課或主講教師簽字：多種排序的串行算法與并行算法的比較摘要排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算，如何進(jìn)行排序，特別是如何進(jìn)行高效的排 序，是計(jì)算機(jī)應(yīng)用中的重要課題。排序的對(duì)象一般是一組記錄組成的文件，而記錄則是由若 干數(shù)據(jù)項(xiàng)組成，其中的一項(xiàng)可用來標(biāo)志一個(gè)記錄，稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。 所謂排序，就是要整理文件中的記錄，使得它按關(guān)鍵字遞增（或遞減）的次序排列起來。若 給定的文件含有n個(gè)記錄R1，R2，Rn，它們的關(guān)鍵字分別為K1，K2，Kn， 要把這n個(gè)

2、記錄重新排列成為 %，Ri2，Rin，使得 K1 3Ki2 33Kin （或 、W Ki2 aj thenk=k+1End ifend forbk= aiend forEnd1.2枚舉排序的并行算法對(duì)該算法的并行化是很簡(jiǎn)單的，假設(shè)對(duì)一個(gè)長(zhǎng)為n的輸入序列使用n個(gè)處理器進(jìn)行排序， 只需是每個(gè)處理器負(fù)責(zé)完成對(duì)其中一個(gè)元素的定位，然后將所有的定位信息集中到主進(jìn)程 中，由主進(jìn)程負(fù)責(zé)完成所有元素的最終排位。該并行算法描述如下： 輸入：無序數(shù)組a1an 輸出：有序數(shù)組b1bnBeginP(播送a1an給所有當(dāng)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個(gè)處理器，由于每個(gè)處理器定位一個(gè)元素，所以步驟的時(shí) 間復(fù)雜度為。(n)；步驟中主進(jìn)程完成的數(shù)組元素重定位操作的時(shí)間復(fù)雜度為0(n)，通 信復(fù)雜度分別為。(n)；同時(shí)中的通信復(fù)雜度為。(n2)；所以總的計(jì)算復(fù)雜度為。(n)， 總的通信復(fù)雜度為。(n2)?？焖倥判?.1快速排序及其串行算法快速排序(Quicksort)是一種最基本的排序算法，它的基本思想是：在當(dāng)前無序區(qū)R1， n中取一個(gè)記錄作為比較的“基準(zhǔn)”(一般取第一

4、個(gè)、最后一個(gè)或中間位置的元素)，用此 基準(zhǔn)將當(dāng)前的無序區(qū)R1，n劃分成左右兩個(gè)無序的子區(qū)R1，i-1和Ri，n(1WiWn)，且 左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，右邊的無序子區(qū)中記錄的所 有關(guān)鍵字均大于等于基準(zhǔn)的關(guān)鍵字；當(dāng)R1，i-1和Ri，n非空時(shí)，分別對(duì)它們重復(fù)上述的 劃分過程，直到所有的無序子區(qū)中的記錄均排好序?yàn)橹?。算?33單處理機(jī)上快速排序算法輸入：無序數(shù)組data1,n輸出：有序數(shù)組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快速排序的并行算法快速排序算法并行化的一個(gè)簡(jiǎn)單思想是，對(duì)每次劃分過后所得到的兩個(gè)序列分別使用兩個(gè) 處理器完成遞歸排序。例如對(duì)一個(gè)長(zhǎng)為n的序列，首先劃分得到兩個(gè)長(zhǎng)為n/2的序列，將其交 給兩個(gè)處理器分別處理；而后進(jìn)一步劃分得到四個(gè)長(zhǎng)為n/4的序列，再分別交給四個(gè)處理器 處理；如此遞歸下去最終得到排序好的序列。當(dāng)然這里舉的是理想的劃分情況，如果劃分步 驟不能達(dá)到平均分配的目的，那么排序的效率會(huì)相對(duì)較差。算法13.4中描述了

6、使用2皿個(gè)處理 器完成對(duì)n個(gè)輸入數(shù)據(jù)排序的并行算法?？焖倥判虿⑿兴惴ǎ狠斎耄簾o序數(shù)組data1,n，使用的處理器個(gè)數(shù)2m輸出：有序數(shù)組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在最優(yōu)的情況下該并行算法形成一個(gè)高度為logn的排序樹，其計(jì)算復(fù)雜度為O (n)， 通信復(fù)雜度也為O (n)。同串行算法一樣，在最壞情況下其計(jì)算復(fù)雜度降為O (n2)。正常 情況下該算法的計(jì)算復(fù)雜度也為O (n)，只不過具有更高的常數(shù)因子。3.PSRS排序3.1PSRS算法原理并行正則采樣排序，簡(jiǎn)稱PSRS(Parallel Sorting by Regular Sampling)它是一種基 于均勻劃分(Uniform Pa

8、rtition)原理的負(fù)載均衡的并行排序算法。假定待排序的元素有 n個(gè)，系統(tǒng)中有p個(gè)處理器，那么系統(tǒng)首先將n個(gè)元素均勻地分割成p段，每段含有n/p個(gè) 元素，每段指派一個(gè)處理器，然后各個(gè)處理器同時(shí)施行局部排序。為了使各段中諸局部有序 的元素在整個(gè)序列中也能占據(jù)正確的位置，那么就首先從各段中抽取幾個(gè)代表元素，再?gòu)乃?們產(chǎn)生出p-1個(gè)主元，然后按這些主元與原各局部有序中的元素之間的偏序關(guān)系，將各個(gè)局 部有序段劃分成p段，接著通過全局交換將各個(gè)段中的對(duì)應(yīng)部分集合在一起，最后將這些集 合在一起的各部分采用多路歸并的方法進(jìn)行排序，這些有序段匯合起來就自然成為全局有序 列了。3.2PSRS算法形式化描述設(shè)有

9、n個(gè)數(shù)據(jù)，P個(gè)處理器，以及均勻分布在P個(gè)處理器上的n個(gè)數(shù)據(jù)。則PSRS算法可描述 如下：PSRS排序算法輸入：n個(gè)待排序的數(shù)據(jù)，均勻地分布在P個(gè)處理器上輸出：分布在各個(gè)處理器上，得到全局有序的數(shù)據(jù)序列Begin每個(gè)處理器將自己的n/P個(gè)數(shù)據(jù)用串行快速排序(Quick sort)，得到一個(gè)排好序的序列；每個(gè)處理器從排好序的序列中選取第w，2w，3w，(P-1)w個(gè)共P-1個(gè)數(shù)據(jù)作為代表元素，其中w=n/P2；每個(gè)處理器將選好的代表元素送到處理器P0中，并將送來的P段有序的數(shù)據(jù)序列做P路歸并，再選擇排序后的第P-1，2(P-1)，(P-1)(P-1)個(gè)共P-1個(gè)主元；處理器P0將這P-1個(gè)主元播送

10、到所有處理器中；每個(gè)處理器根據(jù)上步送來的P-1個(gè)主元把自己的n/P個(gè)數(shù)據(jù)分成P段，記為處j i w理器Pi的第j+1段，其中i=0，P-1，j=0，P-1；每個(gè)處理器送它的第i+1段給處理器Pi，從而使得第i個(gè)處理器含有所有處理器的第i段數(shù)據(jù)(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 .陳國(guó)良編著.并行算法的設(shè)計(jì)與分析(修訂版).高等教育出版社,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每個(gè)處理器再通過P路歸并排序?qū)⑸弦徊降牡降臄?shù)據(jù)排序；從而這n個(gè)數(shù)據(jù)便是有序的END在該算法中，針對(duì)其中的計(jì)算部分中的快速排序的代價(jià)為O(klogk)，其中k=n/p；第 步中各個(gè)處理器選擇P個(gè)主元的代價(jià)為O(P)；中對(duì)P2個(gè)主元進(jìn)行歸并并選取新的主元所 需代價(jià)為O(P2+logP)；中對(duì)數(shù)據(jù)劃分的代價(jià)為O(P+n/p)；最后第步中各個(gè)處理器進(jìn) 行并行歸并的代價(jià)為O(n