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

1、3.1實驗目的與要求1、熟悉快速排序的串行算法2、熟悉快速排序的并行算法 3、實現(xiàn)快速排序的并行算法 3.2 實驗環(huán)境及軟件單臺或聯(lián)網(wǎng)的多臺PC機，Linux操作系統(tǒng)，MPI系統(tǒng)。3.3實驗內(nèi)容1、快速排序的基本思想2、單處理機上快速排序算法3、快速排序算法的性能4、快速排序算法并行化5、描述了使用2m個處理器完成對n個輸入數(shù)據(jù)排序的并行算法。 6、在最優(yōu)的情況下并行算法形成一個高度為logn的排序樹7、完成快速排序的并行實現(xiàn)的流程圖8、完成快速排序的并行算法的實現(xiàn)3.4實驗步驟3.4.1、快速排序（Quick Sort）是一種最基本的排序算法，它的基本思想是：在當前無序區(qū)R1，n中取一個記錄

2、作為比較的“基準”（一般取第一個、最后一個或中間位置的元素），用此基準將當前的無序區(qū)R1，n劃分成左右兩個無序的子區(qū)R1，i-1和Ri，n(1in)，且左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準的關(guān)鍵字，右邊的無序子區(qū)中記錄的所有關(guān)鍵字均大于等于基準的關(guān)鍵字；當R1，i-1和Ri，n非空時，分別對它們重復上述的劃分過程，直到所有的無序子區(qū)中的記錄均排好序為止。 3.4.2、單處理機上快速排序算法輸入：無序數(shù)組data1,n輸出：有序數(shù)組data1,nBegincall procedure quicksort(data,1,n)Endprocedure quicksort(data,i,j)

3、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 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+1End、快速排

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

5、處理；而后進一步劃分得到四個長為n/4的序列，再分別交給四個處理器處理；如此遞歸下去最終得到排序好的序列。當然這里舉的是理想的劃分情況，如果劃分步驟不能達到平均分配的目的，那么排序的效率會相對較差。 3.4.5、描述了使用2m個處理器完成對n個輸入數(shù)據(jù)排序的并行算法。 快速排序并行算法輸入：無序數(shù)組data1,n，使用的處理器個數(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)Pid call

6、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)的情況下該并行算法形成一個高度為logn的排序樹，其計算復雜度為O（n），通信復雜度也為O（n）。同串行算法一樣，在最

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

8、 m,int id,int MyID);QuickSort(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表示進程標志符；SumID表示組內(nèi)進程數(shù)*/intMyID, SumID;int i, j;int m, r;MPI_Status status;/*啟動MPI計算*/MPI_In

9、it(&argc,&argv);/*MPI_COMM_WORLD是通信子*/*確定自己的進程標志符MyID*/MPI_Comm_rank(MPI_COMM_WORLD,&MyID);/*組內(nèi)進程數(shù)是SumID*/MPI_Comm_size(MPI_COMM_WORLD,&SumID);/*根處理機(MyID=0)獲取必要信息，并分配各處理機進行工作*/if(MyID=0)/*獲取待排序數(shù)組的長度*/DataSize=GetDataSize();data=(int *)malloc(DataSize*sizeof(int);/*內(nèi)存分配錯誤*/if(data=0)

10、 ErrMsg("Malloc memory error!");/*動態(tài)生成待排序序列*/srand(396);for(i=0;i<DataSize;i+)datai=(int)rand();printf("%10d",datai);printf("n");m=log2(SumID); /調(diào)用函數(shù):求以2為底的SumID的對數(shù)/* 從根處理器將數(shù)據(jù)序列廣播到其他處理器*/*"1"表示傳送的輸入緩沖中的元素的個數(shù), */* "MPI_INT"表示輸入元素的類型, */ /* "0&

11、quot;表示root processor的ID */MPI_Bcast(&DataSize,1,MPI_INT,0,MPI_COMM_WORLD);/*ID號為0的處理器調(diào)度執(zhí)行排序*/para_QuickSort(data,0,DataSize-1,m,0,MyID); /*ID號為0的處理器打印排序完的有序序列*/if(MyID=0) printf("實際應用處理器數(shù)：%dn ",exp2(m-1);for(i=0;i<DataSize;i+)printf("%10d",datai);printf("n");MPI

12、_Finalize();/結(jié)束計算return 0;/* 函數(shù)名: para_QuickSort* 功能：并行快速排序，對起止位置為start和end的序列，使用2的m次冪個處理器進行排序* 輸入：無序數(shù)組data1,n，使用的處理器個數(shù)2m* 輸出：有序數(shù)組data1,n*/para_QuickSort(int *data,int start,int end,int m,int id,int MyID)int i, j;int r;int MyLength;int *tmp;MPI_Status status;MyLength=-1;/*如果可供選擇的處理器只有一個，那么由處理器id調(diào)用串行

13、排序，對應于算法步驟(1.1)*/*(1.1)Pid call quicksort(data,i,j) */if(m=0)if(MyID=id)QuickSort(data,start,end);return;/*由第id號處理器劃分數(shù)據(jù)，并將后一部分數(shù)據(jù)發(fā)送到處理器id+exp2(m-1)，對應于算法步驟(1.2,1.3)*/*(1.2) Pid: r=patrition(data,i,j)*/if(MyID=id)/*將當前的無序區(qū)R1，n劃分成左右兩個無序的子區(qū)R1，i-1和Ri，n(1in)*/r=Partition(data,start,end);MyLength=end-r; /*

14、(1.3)Pid send datar+1,m-1 to P(id+2m-1) */* MyLength表示發(fā)送緩沖區(qū)地址；*/* 發(fā)送元素數(shù)目為1; */* MyID是消息標簽 */ /* 在下面添加一條語句 發(fā)送長度 */ MPI_Send(&MyLength,1,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);/*若緩沖區(qū)不空，則第id+2m-1號處理器取數(shù)據(jù)的首址是datar+1*/if(MyLength!=0) /* 在下面添加一條語句 */MPI_Send(data+r+1,MyLength ,MPI_INT,id+exp2(m-1),M

15、yID,MPI_COMM_WORLD);/*處理器id+exp2(m-1)接受處理器id發(fā)送的消息*/if(MyID=id+exp2(m-1) /* 在下面添加一條語句 */ MPI_Recv(&MyLength,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);if(MyLength!=0)tmp=(int *)malloc(MyLength*sizeof(int);if(tmp=0) ErrMsg("Malloc memory error!"); /* 在下面添加一條語句 */MPI_Recv(tmp,MyLength,MP

16、I_INT,id,id,MPI_COMM_WORLD,&status);/*遞歸調(diào)用并行排序，對應于算法步驟(1.4，1.5)*/*用2m-1個處理器對start-(r-1)的數(shù)據(jù)進行遞歸排序*/j=r-1-start;MPI_Bcast(&j,1,MPI_INT,id,MPI_COMM_WORLD);/*(1.4)para_quicksort(data,i,r-1,m-1,id)*/if(j>0) /* 在下面添加一條語句 */ para_QuickSort(data,start,r-1,m-1,id,MyID);/*用2m-1個處理器對(r+1)-end的數(shù)據(jù)進行遞歸

17、排序*/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(j>0)/* 在下面添加一條語句 */ para_QuickSort(tmp,0,MyLength-1,m-1,id+exp2(m-1),MyID);/*將排序好的數(shù)據(jù)由處理器id+exp2(m-1)發(fā)回id號處理器，對應于算法步驟(1.6)*/*(1.6)P(id+2m-1) send datar+1,m-1 back to Pid */if(MyID=id+exp2

18、(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(data+r+1,MyLength,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);/* 函數(shù)名: QuickSort* 功能：對起止位置為start和end的數(shù)組序列，進行串行快速排序。* 輸入：無序數(shù)組data1,n* 返回：有序數(shù)組data1,

19、n*/QuickSort(int *data,int start,int end)int r;int i;if(start<end)r=Partition(data,start,end);QuickSort(data,start,r-1);QuickSort(data,r+1,end);return 0;/* 函數(shù)名: Partition* 功能：對起止位置為start和end的數(shù)組序列，將其分成兩個非空子序列，*其中前一個子序列中的任意元素小于后個子序列的元素。* 輸入：無序數(shù)組data1,n* 返回: 兩個非空子序列的分界下標*/int Partition(int *data,int

20、 start,int end)int pivo;int i, j;int tmp;pivo=dataend;i=start-1;/*i(活動指針)*/for(j=start;j<end;j+)if(dataj<=pivo)i+;/*i表示比pivo小的元素的個數(shù)*/tmp=datai;datai=dataj;dataj=tmp;tmp=datai+1;datai+1=dataend;dataend=tmp;/*以pivo為分界，datai+1=pivo*/return i+1;/* 函數(shù)名: exp2* 功能：求2的num次冪* 輸入：int型數(shù)據(jù)num* 返回: 2的num次冪*

21、/int exp2(int num)int i;i=1;while(num>0)num-;i=i*2;return i;/* 函數(shù)名: log2* 功能：求以2為底的num的對數(shù)* 輸入：int型數(shù)據(jù)num* 返回: 以2為底的num的對數(shù)*/int log2(int num)int i, j;i=1;j=2;while(j<num)j=j*2;i+;if(j>num)i-;return i;/* 函數(shù)名: GetDataSize* 功能：讀入待排序序列長度*/int GetDataSize()int i;while(TRUE)printf("Input the D

22、ata Size :");scanf("%d",&i);/*讀出正確的i，返回；否則，繼續(xù)要求輸入*/if(i>0) && (i<=65535)break;ErrMsg("Wrong Data Size, must between 1.65535");return i;/*輸出錯誤信息*/ErrMsg(char *msg)printf("Error: %s n",msg);3.5 實驗結(jié)果3.6實驗總結(jié)通過這次實驗，我熟悉快速排序的串行算法和并行算法 ，并了解了實現(xiàn)快速排序的并行流程圖。但

23、是在實際的操作過程中也遇到了不少問題。最后是在同學的幫助下完成的。一、枚舉排序算法說明：    枚舉排序（Enumeration Sort）是一種最為簡單的排序算法，通常也被叫做秩排序（Rank Sort）。    該算法的基本思想是：對每一個要排序的元素統(tǒng)計小于它的所有元素的個數(shù)，從而得到該元素在整個序列中的位置。其時間復雜度為o(n2)。其偽代碼為：    輸入為：a1, a2 , . , an    輸出為：b1, b2 , ., bn    for i =1 to n do&#

24、160;       1)k =1        2)for j = 1 to n do              if a > aj then                k= k + 1            endif          endfor

25、60;         3)bk = a    endfor    算法思想很簡單，現(xiàn)將其主要代碼總結(jié)如下：    1、數(shù)組自動生成，隨機生成長度為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:   

26、60; 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.   1

27、1:  復制代碼2、取得每個元素在數(shù)組中的秩，即統(tǒng)計每個元素按小于它的其他所有元素的個數(shù)：1.   1:  int *get_array_elem_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:  1

28、0.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+

29、)18.19.   10:              if(init_array < init_arrayj)20.21.   11:                  k+;22.23.   12:              if(init_array = init_arrayj) && i >j)24.25

30、.   13:                  k+;26.27.   14:          28.29.   15:  30.31.   16:          positioni-start = k;32.33.   17:      34.35.   18:  36

31、.37.   19:      return position;38.39.   20:  復制代碼其中my_malloc函數(shù)的作用為動態(tài)分配大小為size的空間，如分配失敗，則終止程序：1.   1:  void *my_malloc(int malloc_size)2.3.   2:      void *buffer;4.5.   3:  6.7.   4:      if(buffer = (voi

32、d *)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:  復制代碼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 *ini