并行计算实验快速排序的并行算法

1、-作者xxxx-日期xxxx并行计算实验快速排序的并行算法【精品文档】1、熟悉快速排序的串行算法2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件单台或联网的多台PC机，Linux操作系统，MPI系统。1、快速排序的基本思想2、单处理机上快速排序算法3、快速排序算法的性能4、快速排序算法并行化5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树7、完成快速排序的并行实现的流程图8、完成快速排序的并行算法的实现3.4.1、快速排序（Quick Sort）是一种最基本的排序算法，它的基本思想是：在当前无序

2、区R1，n中取一个记录作为比较的“基准”（一般取第一个、最后一个或中间位置的元素），用此基准将当前的无序区R1，n划分成左右两个无序的子区R1，i-1和Ri，n(1in)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字；当R1，i-1和Ri，n非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止。 3.4.2、单处理机上快速排序算法输入：无序数组data1,n输出：有序数组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、快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。在最坏的情况下，划分的结果是一边有n-1个元素，而另一边有0个元素（除去被选中的基准元素）。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是（n2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为O（nlogn）。在一般的情况下该算法仍能保持O（nlogn）的复杂度，只不过其具有更高的常数因子。、快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给

5、两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。 3.4.5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 快速排序并行算法输入：无序数组data1,n，使用的处理器个数2m输出：有序数组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、在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O（n），通信复杂度也为O（n）。同串行

7、算法一样，在最坏情况下其计算复杂度降为O（n2）。正常情况下该算法的计算复杂度也为O（n），只不过具有更高的常数因子。、完成快速排序的并行实现的流程图3.4.8、完成快速排序的并行算法的实现#include #include #define TRUE 1 /* 函数名: main* 功能：实现快速排序的主程序* 输入：argc为命令行参数个数；* argv为每个命令行参数组成的字符串数组。* 输出：返回0代表程序正常结束*/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表示进程标志符；SumID表示组内进程数*/intMyID, SumID;int i, j;int m, r;MPI_Status status;/*启动MPI计算*/MPI_Init(&argc,&argv);/*MPI_

9、COMM_WORLD是通信子*/*确定自己的进程标志符MyID*/MPI_Comm_rank(MPI_COMM_WORLD,&MyID);/*组内进程数是SumID*/MPI_Comm_size(MPI_COMM_WORLD,&SumID);/*根处理机(MyID=0)获取必要信息，并分配各处理机进行工作*/if(MyID=0)/*获取待排序数组的长度*/DataSize=GetDataSize();data=(int *)malloc(DataSize*sizeof(int);/*内存分配错误*/if(data=0) ErrMsg(Malloc memory error!);/*动态生成待排

10、序序列*/srand(396);for(i=0;iDataSize;i+)datai=(int)rand();printf(%10d,datai);printf(n);m=log2(SumID); /调用函数:求以2为底的SumID的对数/* 从根处理器将数据序列广播到其他处理器*/*1表示传送的输入缓冲中的元素的个数, */* MPI_INT表示输入元素的类型, */ /* 0表示root processor的ID */MPI_Bcast(&DataSize,1,MPI_INT,0,MPI_COMM_WORLD);/*ID号为0的处理器调度执行排序*/para_QuickSort(data,

11、0,DataSize-1,m,0,MyID); /*ID号为0的处理器打印排序完的有序序列*/if(MyID=0) printf(实际应用处理器数：%dn ,exp2(m-1);for(i=0;i0) /* 在下面添加一条语句 */ para_QuickSort(data,start,r-1,m-1,id,MyID);/*用2m-1个处理器对(r+1)-end的数据进行递归排序*/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);/*将排序好的数据由处理器id+exp2(m-1)发回id号处理器，对应于算法步骤(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);/* 函数名: QuickSort* 功能：对起止位置为start和end的数组序列，进行串行快速排序。* 输入：无序数组data1,n* 返回：有序数组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;/* 函数名: Partition* 功能：对起止位置为start和end的数组序列，将其分成两个非空子序列，*其中前一个子序列中的任意元素小于后个子序列的元素。* 输入：无序数组data1,n* 返回: 两个非空子序列的分界下标*/int Partition(int *data,int start,int end)int pivo;int i, j;int tmp;pivo=dataend;i=start-1;/*i(活动指针)*/for(j=start;jend;j+)if(dataj0)num-;i=i*2;return i;/* 函数名: log2* 功能：求以2为

15、底的num的对数* 输入：int型数据num* 返回: 以2为底的num的对数*/int log2(int num)int i, j;i=1;j=2;while(jnum)i-;return i;/* 函数名: GetDataSize* 功能：读入待排序序列长度*/int GetDataSize()int i;while(TRUE)printf(Input the Data Size :);scanf(%d,&i);/*读出正确的i，返回；否则，继续要求输入*/if(i0) & (i aj then k= k + 1 endif endfor 3)bk = a endfor 算法思想很简单，现

16、将其主要代码总结如下： 1、数组自动生成，随机生成长度为n的数组：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: 复制代码2、取得每个元素在数组中的秩，即统计每个元素按小于它的其他所有元素的个数：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: 复制代码其中my_malloc函数的作用为动态分配大小为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: 复制代码3、 算法主函数：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.