并行計算實驗快速排序的并行算法

《并行計算實驗快速排序的并行算法》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

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

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

3、為止。3.4.2、單處理機上快速排序算法輸入：無序數組data[1,n]輸出：有序數組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、快速排序算法的性能主要決定于輸入數組的劃分是否均衡，而這與基準元素的選擇密切相關。在最壞的情況下，劃分的結果是一邊有n-1個元素，而另一邊有0個元素（除去被選中的基準元素）。如果每次遞歸排序中的劃分都產生這種極度的不平衡，那么整個算法的復雜度將是Θ（n2）。在最好的情況下，每次劃分都使得輸入數組平均分為兩半，那么算法的復雜度為O（nlogn）。在一般的情況下該

5、算法仍能保持O（nlogn）的復雜度，只不過其具有更高的常數因子。3.4.4、快速排序算法并行化的一個簡單思想是，對每次劃分過后所得到的兩個序列分別使用兩個處理器完成遞歸排序。例如對一個長為n的序列，首先劃分得到兩個長為n/2的序列，將其交給兩個處理器分別處理；而后進一步劃分得到四個長為n/4的序列，再分別交給四個處理器處理；如此遞歸下去最終得到排序好的序列。當然這里舉的是理想的劃分情況，如果劃分步驟不能達到平均分配的目的，那么排序的效率會相對較差。3.4.5、描述了使用2m個處理器完成對n個輸入數據排序的并行算法。快速排序并行算法輸入：無序數組data[1,n]，使用的處理器個數2

6、m輸出：有序數組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)的情況下該并行算法形成一個高度為logn的排序樹，其計算復雜度為O（n），通信復雜度也為O（n）。同串行算法一樣，在最壞情況下其計算復雜度降為O（n2）。正常情況下該算法的計算復雜度也為O（n），只不過具有更高的常數因子。3.4.7、完成快速排序的并行實現的流程圖3.4.8、完成快速排序的并行算法的實現#include#