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

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

2、作為比較的“基準(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í)，分別對它們重復(fù)上述的劃分過程，直到所有的無序子區(qū)中的記錄均排好序?yàn)橹埂?3.4.2、單處理機(jī)上快速排序算法輸入：無序數(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+1End3.4.

4、3、快速排序算法的性能主要決定于輸入數(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ù)因子。3.4.4、快速排序算法并行化的一個(gè)簡單思想是，對每次劃分過后所得到的兩個(gè)序列分別使用兩個(gè)處理器完成遞歸排序。例如對一個(gè)長為n的序列，首先劃分得到兩個(gè)長為n/2的序列，將

5、其交給兩個(gè)處理器分別處理；而后進(jìn)一步劃分得到四個(gè)長為n/4的序列，再分別交給四個(gè)處理器處理；如此遞歸下去最終得到排序好的序列。當(dāng)然這里舉的是理想的劃分情況，如果劃分步驟不能達(dá)到平均分配的目的，那么排序的效率會相對較差。 3.4.5、描述了使用2m個(gè)處理器完成對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

6、)Pid 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ù)因子。3.4.7、完成快速排序的并行實(shí)現(xiàn)的流程圖3.4.8、完成快速排序的并行算法的實(shí)現(xiàn)#include <stdlib.h>#include <mpi.h>#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 st

8、art,int end,int 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表示進(jìn)程標(biāo)志符；SumID表示組內(nèi)進(jìn)程數(shù)*/intMyID, SumID;int i, j;int m, r;MPI_Status status;/*

9、啟動MPI計(jì)算*/MPI_Init(&argc,&argv);/*MPI_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)存分

10、配錯(cuò)誤*/if(data=0) 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"表示傳送的輸入緩沖中的元素的個(gè)數(shù), */* "MPI_INT"表示輸入元素的類型,

11、 */ /* "0"表示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í)際應(yīng)用處理器數(shù)：%dn ",exp2(m-1);for(i=0;i<DataSize;i+)printf("%10d",datai);printf(&qu

12、ot;n");MPI_Finalize();/結(jié)束計(jì)算return 0;/* 函數(shù)名: para_QuickSort* 功能：并行快速排序，對起止位置為start和end的序列，使用2的m次冪個(gè)處理器進(jìn)行排序* 輸入：無序數(shù)組data1,n，使用的處理器個(gè)數(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;/*如果可供選擇的處理器只有

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

14、ength=end-r; /*(1.3)Pid send datar+1,m-1 to P(id+2m-1) */* MyLength表示發(fā)送緩沖區(qū)地址；*/* 發(fā)送元素?cái)?shù)目為1; */* MyID是消息標(biāo)簽 */ /* 在下面添加一條語句 發(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

15、,id+exp2(m-1),MyID,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(

16、tmp,MyLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);/*遞歸調(diào)用并行排序，對應(yīng)于算法步驟(1.4，1.5)*/*用2m-1個(gè)處理器對start-(r-1)的數(shù)據(jù)進(jìn)行遞歸排序*/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個(gè)處理器對(

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

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

19、* 返回：有序數(shù)組data1,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ù)組序列，將其分成兩個(gè)非空子序列，*其中前一個(gè)子序列中的任意元素小于后個(gè)子序列的元素。* 輸入：無序數(shù)組data1,n* 返回: 兩個(gè)非空子序列的分界下標(biāo)*/int Partitio

20、n(int *data,int 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小的元素的個(gè)數(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ù)nu

21、m* 返回: 2的num次冪*/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(&q

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

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

24、 i =1 to n do        1)k =1        2)for j = 1 to n do              if a > aj then                k= k + 1            endif        &

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

26、160;     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;

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

28、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 < a

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

30、; i >j)24.25.   13:                  k+;26.27.   14:          28.29.   15:  30.31.   16:          positioni-start = k;32.33.   17:      34.35.   18

31、:  36.37.   19:      return position;38.39.   20:  復(fù)制代碼其中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:      i

32、f(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 *in