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

1、-作者xxxx-日期xxxx并行計(jì)算實(shí)驗(yàn)快速排序的并行算法【精品文檔】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)。1、快速排序的基本思想2、單處理機(jī)上快速排序算法3、快速排序算法的性能4、快速排序算法并行化5、描述了使用2m個(gè)處理器完成對(duì)n個(gè)輸入數(shù)據(jù)排序的并行算法。 6、在最優(yōu)的情況下并行算法形成一個(gè)高度為logn的排序樹7、完成快速排序的并行實(shí)現(xiàn)的流程圖8、完成快速排序的并行算法的實(shí)現(xiàn)3.4.1、快速排序（Quick Sort）是一種最基本的排序算法，它的基本思想是：在當(dāng)前無序

2、區(qū)R1，n中取一個(gè)記錄作為比較的“基準(zhǔn)”（一般取第一個(gè)、最后一個(gè)或中間位置的元素），用此基準(zhǔn)將當(dāng)前的無序區(qū)R1，n劃分成左右兩個(gè)無序的子區(qū)R1，i-1和Ri，n(1in)，且左邊的無序子區(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)橹埂?3.4.2、單處理機(jī)上快速排序算法輸入：無序數(shù)組data1,n輸出：有序數(shù)組data1,nBegincall procedure quicksort(data,1,n)Endprocedure quicksor

3、t(data,i,j)Begin(1)if (ij) then (1.1)r = partition(data,i,j)(1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j);end ifEndprocedure partition(data,k,l)Begin(1)pivo=datal(2)i=k-1(3)for j=k to l-1 doif datajpivo theni=i+1exchange datai and datajend ifend for(4)exchange datai+1 and datal(5)return i+1

4、End、快速排序算法的性能主要決定于輸入數(shù)組的劃分是否均衡，而這與基準(zhǔn)元素的選擇密切相關(guān)。在最壞的情況下，劃分的結(jié)果是一邊有n-1個(gè)元素，而另一邊有0個(gè)元素（除去被選中的基準(zhǔn)元素）。如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個(gè)算法的復(fù)雜度將是（n2）。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為O（nlogn）。在一般的情況下該算法仍能保持O（nlogn）的復(fù)雜度，只不過其具有更高的常數(shù)因子。、快速排序算法并行化的一個(gè)簡單思想是，對(duì)每次劃分過后所得到的兩個(gè)序列分別使用兩個(gè)處理器完成遞歸排序。例如對(duì)一個(gè)長為n的序列，首先劃分得到兩個(gè)長為n/2的序列，將其交給

5、兩個(gè)處理器分別處理；而后進(jìn)一步劃分得到四個(gè)長為n/4的序列，再分別交給四個(gè)處理器處理；如此遞歸下去最終得到排序好的序列。當(dāng)然這里舉的是理想的劃分情況，如果劃分步驟不能達(dá)到平均分配的目的，那么排序的效率會(huì)相對(duì)較差。 3.4.5、描述了使用2m個(gè)處理器完成對(duì)n個(gè)輸入數(shù)據(jù)排序的并行算法。 快速排序并行算法輸入：無序數(shù)組data1,n，使用的處理器個(gè)數(shù)2m輸出：有序數(shù)組data1,nBeginpara_quicksort(data,1,n,m,0)Endprocedure para_quicksort(data,i,j,m,id)Begin(1)if (j-i)k or m=0 then(1.1)Pi

6、d call quicksort(data,i,j) else (1.2)Pid: r=patrition(data,i,j) (1.3)P id send datar+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-1 send datar+1,m-1 back to Pid end if End3.4.6、在最優(yōu)的情況下該并行算法形成一個(gè)高度為logn的排序樹，其計(jì)算復(fù)雜度為O（n），通信復(fù)雜度也為O（n）。同串行

7、算法一樣，在最壞情況下其計(jì)算復(fù)雜度降為O（n2）。正常情況下該算法的計(jì)算復(fù)雜度也為O（n），只不過具有更高的常數(shù)因子。、完成快速排序的并行實(shí)現(xiàn)的流程圖3.4.8、完成快速排序的并行算法的實(shí)現(xiàn)#include #include #define TRUE 1 /* 函數(shù)名: main* 功能：實(shí)現(xiàn)快速排序的主程序* 輸入：argc為命令行參數(shù)個(gè)數(shù)；* argv為每個(gè)命令行參數(shù)組成的字符串?dāng)?shù)組。* 輸出：返回0代表程序正常結(jié)束*/int GetDataSize();para_QuickSort(int *data,int start,int end,int m,int id,int MyID);Qu

8、ickSort(int *data,int start,int end);int Partition(int *data,int start,int end);int exp2(int num);int log2(int num);ErrMsg(char *msg);main(int argc,char *argv)int DataSize;int *data;/*MyID表示進(jìn)程標(biāo)志符；SumID表示組內(nèi)進(jìn)程數(shù)*/intMyID, SumID;int i, j;int m, r;MPI_Status status;/*啟動(dòng)MPI計(jì)算*/MPI_Init(&argc,&argv);/*MPI_

9、COMM_WORLD是通信子*/*確定自己的進(jìn)程標(biāo)志符MyID*/MPI_Comm_rank(MPI_COMM_WORLD,&MyID);/*組內(nèi)進(jìn)程數(shù)是SumID*/MPI_Comm_size(MPI_COMM_WORLD,&SumID);/*根處理機(jī)(MyID=0)獲取必要信息，并分配各處理機(jī)進(jìn)行工作*/if(MyID=0)/*獲取待排序數(shù)組的長度*/DataSize=GetDataSize();data=(int *)malloc(DataSize*sizeof(int);/*內(nèi)存分配錯(cuò)誤*/if(data=0) ErrMsg(Malloc memory error!);/*動(dòng)態(tài)生成待排

10、序序列*/srand(396);for(i=0;iDataSize;i+)datai=(int)rand();printf(%10d,datai);printf(n);m=log2(SumID); /調(diào)用函數(shù):求以2為底的SumID的對(duì)數(shù)/* 從根處理器將數(shù)據(jù)序列廣播到其他處理器*/*1表示傳送的輸入緩沖中的元素的個(gè)數(shù), */* MPI_INT表示輸入元素的類型, */ /* 0表示root processor的ID */MPI_Bcast(&DataSize,1,MPI_INT,0,MPI_COMM_WORLD);/*ID號(hào)為0的處理器調(diào)度執(zhí)行排序*/para_QuickSort(data,

11、0,DataSize-1,m,0,MyID); /*ID號(hào)為0的處理器打印排序完的有序序列*/if(MyID=0) printf(實(shí)際應(yīng)用處理器數(shù)：%dn ,exp2(m-1);for(i=0;i0) /* 在下面添加一條語句 */ para_QuickSort(data,start,r-1,m-1,id,MyID);/*用2m-1個(gè)處理器對(duì)(r+1)-end的數(shù)據(jù)進(jìn)行遞歸排序*/j=MyLength;MPI_Bcast(&j,1,MPI_INT,id,MPI_COMM_WORLD);/*(1.5)para_quicksort(data,r+1,j,m-1,id+2m-1)*/if(j0)/*

12、 在下面添加一條語句 */ para_QuickSort(tmp,0,MyLength-1,m-1,id+exp2(m-1),MyID);/*將排序好的數(shù)據(jù)由處理器id+exp2(m-1)發(fā)回id號(hào)處理器，對(duì)應(yīng)于算法步驟(1.6)*/*(1.6)P(id+2m-1) send datar+1,m-1 back to Pid */if(MyID=id+exp2(m-1) & (MyLength!=0)MPI_Send(tmp,MyLength,MPI_INT,id,id+exp2(m-1),MPI_COMM_WORLD);if(MyID=id) & (MyLength!=0)MPI_Recv(d

13、ata+r+1,MyLength,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);/* 函數(shù)名: QuickSort* 功能：對(duì)起止位置為start和end的數(shù)組序列，進(jìn)行串行快速排序。* 輸入：無序數(shù)組data1,n* 返回：有序數(shù)組data1,n*/QuickSort(int *data,int start,int end)int r;int i;if(startend)r=Partition(data,start,end);QuickSort(data,start,r-1);QuickSort(data,r+1,end)

14、;return 0;/* 函數(shù)名: Partition* 功能：對(duì)起止位置為start和end的數(shù)組序列，將其分成兩個(gè)非空子序列，*其中前一個(gè)子序列中的任意元素小于后個(gè)子序列的元素。* 輸入：無序數(shù)組data1,n* 返回: 兩個(gè)非空子序列的分界下標(biāo)*/int Partition(int *data,int start,int end)int pivo;int i, j;int tmp;pivo=dataend;i=start-1;/*i(活動(dòng)指針)*/for(j=start;jend;j+)if(dataj0)num-;i=i*2;return i;/* 函數(shù)名: log2* 功能：求以2為

15、底的num的對(duì)數(shù)* 輸入：int型數(shù)據(jù)num* 返回: 以2為底的num的對(duì)數(shù)*/int log2(int num)int i, j;i=1;j=2;while(jnum)i-;return i;/* 函數(shù)名: GetDataSize* 功能：讀入待排序序列長度*/int GetDataSize()int i;while(TRUE)printf(Input the Data Size :);scanf(%d,&i);/*讀出正確的i，返回；否則，繼續(xù)要求輸入*/if(i0) & (i aj then k= k + 1 endif endfor 3)bk = a endfor 算法思想很簡單，現(xiàn)

16、將其主要代碼總結(jié)如下： 1、數(shù)組自動(dòng)生成，隨機(jī)生成長度為n的數(shù)組：1. 1: void array_builder(int *a, int n)2.3. 2: 4.5. 3: int i;6.7. 4:8.9. 5: srand(int)time(0);10.11. 6: 12.13. 7: for(i = 0; i n; i+)14.15. 8: a = (int)rand() % 100;16.17. 9: 18.19. 10: return;20.21. 11: 復(fù)制代碼2、取得每個(gè)元素在數(shù)組中的秩，即統(tǒng)計(jì)每個(gè)元素按小于它的其他所有元素的個(gè)數(shù)：1. 1: int *get_array_e

17、lem_position(int *init_array, int array_length, int start, int size)2.3. 2:4.5. 3: int i,j,k;6.7. 4: int *position;8.9. 5:10.11. 6: position = (int *)my_malloc(sizeof(int) * size);12.13. 7: for(i = start; i start+size; i+)14.15. 8: k = 0;16.17. 9: for(j = 0; j array_length; j+)18.19. 10: if(init_arr

18、ay j)24.25. 13: k+;26.27. 14: 28.29. 15:30.31. 16: positioni-start = k;32.33. 17: 34.35. 18:36.37. 19: return position;38.39. 20: 復(fù)制代碼其中my_malloc函數(shù)的作用為動(dòng)態(tài)分配大小為size的空間，如分配失敗，則終止程序：1. 1: void *my_malloc(int malloc_size)2.3. 2: void *buffer;4.5. 3:6.7. 4: if(buffer = (void *)malloc(size_t)malloc_size) = NULL)8.9. 5: printf(malloc failure);10.11. 6: exit(EXIT_FAILURE);12.13. 7: 14.15. 8:16.17. 9: return buffer;18.19. 10: 復(fù)制代碼3、 算法主函數(shù)：1. 1: void serial()2.3. 2:4.5. 3: int i;6.7. 4: int array_length = ARRAY_LENGTH;8.9. 5:10.11. 6: int *init_array;12.13.