并行計(jì)算實(shí)驗(yàn)快速排序的并行算法

《并行計(jì)算實(shí)驗(yàn)快速排序的并行算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、華南師范大學(xué)實(shí)驗(yàn)報(bào)告學(xué)生姓名學(xué)號(hào)專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)、班級(jí)課程名稱(chēng)并行計(jì)算實(shí)驗(yàn)項(xiàng)目快速排序的并行算法√√√√√√√√√55√√√√實(shí)驗(yàn)類(lèi)型驗(yàn)證設(shè)計(jì)綜合實(shí)驗(yàn)時(shí)間2010年5月10日實(shí)驗(yàn)指導(dǎo)老師實(shí)驗(yàn)評(píng)分3.1實(shí)驗(yàn)?zāi)康呐c要求1、熟悉快速排序的串行算法2、熟悉快速排序的并行算法3、實(shí)現(xiàn)快速排序的并行算法3.2實(shí)驗(yàn)環(huán)境及軟件單臺(tái)或聯(lián)網(wǎng)的多臺(tái)PC機(jī)，Linux操作系統(tǒng)，MPI系統(tǒng)。3.3實(shí)驗(yàn)內(nèi)容1、快速排序的基本思想2、單處理機(jī)上快速排序算法3、快速排序算法的性能4、快速排序算法并行化5、描述了使用2m個(gè)處理器完成對(duì)n個(gè)輸入數(shù)據(jù)排序的并行算法。6、在最優(yōu)的情況下并行算法形成一個(gè)高度為logn

2、的排序樹(shù)7、完成快速排序的并行實(shí)現(xiàn)的流程圖8、完成快速排序的并行算法的實(shí)現(xiàn)3.4實(shí)驗(yàn)步驟3.4.1、快速排序（QuickSort）是一種最基本的排序算法，它的基本思想是：在當(dāng)前無(wú)序區(qū)R[1，n]中取一個(gè)記錄作為比較的“基準(zhǔn)”（一般取第一個(gè)、最后一個(gè)或中間位置的元素），用此基準(zhǔn)將當(dāng)前的無(wú)序區(qū)R[1，n]劃分成左右兩個(gè)無(wú)序的子區(qū)R[1，i-1]和R[i，n](1≤i≤n)，且左邊的無(wú)序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，右邊的無(wú)序子區(qū)中記錄的所有關(guān)鍵字均大于等于基準(zhǔn)的關(guān)鍵字；當(dāng)R[1，i-1]和R[i，n]非空時(shí)，分別對(duì)它們重復(fù)上述的劃分過(guò)程，直到所有的無(wú)序子區(qū)中的記錄均排好序

3、為止。3.4.2、單處理機(jī)上快速排序算法輸入：無(wú)序數(shù)組data[1,n]輸出：有序數(shù)組data[1,n]Begincallprocedurequicksort(data,1,n)Endprocedurequicksort(data,i,j)Begin(1)if(i

4、-1doifdata[j]≤pivotheni=i+1exchangedata[i]anddata[j]endifendfor(4)exchangedata[i+1]anddata[l](5)returni+1End3.4.3、快速排序算法的性能主要決定于輸入數(shù)組的劃分是否均衡，而這與基準(zhǔn)元素的選擇密切相關(guān)。在最壞的情況下，劃分的結(jié)果是一邊有n-1個(gè)元素，而另一邊有0個(gè)元素（除去被選中的基準(zhǔn)元素）。如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個(gè)算法的復(fù)雜度將是Θ（n2）。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為O（nlogn）。在一般的情況下該

5、算法仍能保持O（nlogn）的復(fù)雜度，只不過(guò)其具有更高的常數(shù)因子。3.4.4、快速排序算法并行化的一個(gè)簡(jiǎn)單思想是，對(duì)每次劃分過(guò)后所得到的兩個(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ì)較差。3.4.5、描述了使用2m個(gè)處理器完成對(duì)n個(gè)輸入數(shù)據(jù)排序的并行算法?？焖倥判虿⑿兴惴ㄝ斎耄簾o(wú)序數(shù)組data[1,n]，使用的處理器個(gè)數(shù)2

6、m輸出：有序數(shù)組data[1,n]Beginpara_quicksort(data,1,n,m,0)Endprocedurepara_quicksort(data,i,j,m,id)Begin(1)if(j-i)≤korm=0then(1.1)Pidcallquicksort(data,i,j)else(1.2)Pid:r=patrition(data,i,j)(1.3)Pidsenddata[r+1,m-1]toPid+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

7、-1)(1.6)Pid+2m-1senddata[r+1,m-1]backtoPidendifEnd3.4.6、在最優(yōu)的情況下該并行算法形成一個(gè)高度為logn的排序樹(shù)，其計(jì)算復(fù)雜度為O（n），通信復(fù)雜度也為O（n）。同串行算法一樣，在最壞情況下其計(jì)算復(fù)雜度降為O（n2）。正常情況下該算法的計(jì)算復(fù)雜度也為O（n），只不過(guò)具有更高的常數(shù)因子。3.4.7、完成快速排序的并行實(shí)現(xiàn)的流程圖3.4.8、完成快速排序的并行算法的實(shí)現(xiàn)#include#