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

3.1实验目的与要求1、熟悉快速排序的串行算法2、熟悉快速排序的并行算法3、实现快速排序的并行算法3.2实验环境及软件单台或联网的多台PC机，Linux操作系统，MPI系统。3.3实验内容1、快速排序的基本思想2、单处理机上快速排序算法3、快速排序算法的性能4、快速排序算法并行化5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。6、在最优的情况下并行算法形成一个高度为logn的排序树7、完成快速排序的并行实现的流程图8、完成快速排序的并行算法的实现3.4实验步骤3.4.1、快速排序（QuickSort）是一种最基本的排序算法，它的基本思想是：在当前无序区R[1，n]中取一个记录作为比较的“基准”（一般取第一个、最后一个或中间位置的元素），用此基准将当前的无序区R[1，n]划分成左右两个无序的子区R[1，i-1]和R[i，n](1≤i≤n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字；当R[1，i-1]和R[i，n]非空时，分别对它们重复上述的划分过程，直到所有的无序子区中的记录均排好序为止。3.4.2、单处理机上快速排序算法输入：无序数组data[1,n]输出：有序数组data[1,n]Begincallprocedurequicksort(data,1,n)Endprocedurequicksort(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);endifEndprocedurepartition(data,k,l)Begin(1)pivo=data[l](2)i=k-1(3)forj=ktol-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）。在一般的情况下该算法仍能保持O（nlogn）的复杂度，只不过其具有更高的常数因子。3.4.4、快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。3.4.5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。快速排序并行算法输入：无序数组data[1,n]，使用的处理器个数2m输出：有序数组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-1)(1.6)Pid+2m-1senddata[r+1,m-1]backtoPidendifEnd3.4.6、在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O（n），通信复杂度也为O（n）。同串行算法一样，在最坏情况下其计算复杂度降为O（n2）。正常情况下该算法的计算复杂度也为O（n），只不过具有更高的常数因子。3.4.7、完成快速排序的并行实现的流程图3.4.8、完成快速排序的并行算法的实现#includestdlib.h#includempi.h#defineTRUE1/**函数名:main*功能：实现快速排序的主程序*输入：argc为命令行参数个数；*argv为每个命令行参数组成的字符串数组。*输出：返回0代表程序正常结束初始化MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&MyID);MPI_Comm_size(MPI_COMM_WORLD,&SumID);处理机(MyID=0)获取待排序数组的长度动态生成待排序序列从根处理器将数据序列广播到其他处理器MPI_Bcast调度执行排序para_QuickSort(data,0,DataSize-1,m,0,MyID);ID号为0的处理器打印排序完的有序序列由第id号处理器划分数据，并将后一部分数据发送到处理器id+exp2(m-1)(1.3)Pidsenddata[r+1,end]toP(id+2m-1)MPI_Send(&MyLength,1,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);MPI_Send(data+r+1,MyLength,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);(1.2)Pid:r=patrition(data,i,j)r=Partition(data,start,end);处理器id+exp2(m-1)接受处理器id发送的消息递归调用并行排序用2^m-1个处理器对start--(r-1)的数据进行递归排序用2^m-1个处理器对(r+1)--end的数据进行递归排序将排序好的数据由处理器id+exp2(m-1)发回id号处理器*/intGetDataSize();para_QuickSort(int*data,intstart,intend,intm,intid,intMyID);QuickSort(int*data,intstart,intend);intPartition(int*data,intstart,intend);intexp2(intnum);intlog2(intnum);ErrMsg(char*msg);main(intargc,char*argv[]){intDataSize;int*data;/*MyID表示进程标志符；SumID表示组内进程数*/intMyID,SumID;inti,j;intm,r;MPI_Statusstatus;/*启动MPI计算*/MPI_Init(&argc,&argv);/*MPI_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(Mallocmemoryerror!);/*动态生成待排序序列*/srand(396);for(i=0;iDataSize;i++){data[i]=(int)rand();printf(%10d,data[i]);}printf(\n);}m=log2(SumID);//调用函数:求以2为底的SumID的对数/*从根处理器将数据序列广播到其他处理器*//*{1表示传送的输入缓冲中的元素的个数,*//*MPI_INT表示输入元素的类型,*//*0表示rootprocessor的ID}*/MPI_Bcast(&DataSize,1,MPI_INT,0,MPI_COMM_WORLD);/*ID号为0的处理器调度执行排序*/para_QuickSort(data,0,DataSize-1,m,0,MyID);/*ID号为0的处理器打印排序完的有序序列*/if(MyID==0){printf(实际应用处理器数：%d\n,exp2(m-1));for(i=0;iDataSize;i++){printf(%10d,data[i]);}printf(\n);}MPI_Finalize();//结束计算return0;}/**函数名:para_QuickSort*功能：并行快速排序，对起止位置为start和end的序列，使用2的m次幂个处理器进行排序*输入：无序数组data[1,n]，使用的处理器个数2^m*输出：有序数组data[1,n]*/para_QuickSort(int*data,intstart,intend,intm,intid,intMyID){inti,j;intr;intMyLength;int*tmp;MPI_Statusstatus;MyLength=-1;/*如果可供选择的处理器只有一个，那么由处理器id调用串行排序，对应于算法步骤(1.1)*//*(1.1)Pidcallquicksort(data,i,j)*/if(m==0){if(MyID==id)QuickSort(data,start,end);return;}/*由第id号处理器划分数据，并将后一部分数据发送到处理器id+exp2(m-1)，对应于算法步骤(1.2,1.3)*//*(1.2)Pid:r=patrition(data,i,j)*/if(MyID==id){/*将当前的无序区R[1，n]划分成左右两个无序的子区R[1，i-1]和R[i，n](1≤i≤n)*/r=Partition(data,start,end);MyLength=end-r;/*(1.3)Pidsenddata[r+1,m-1]toP(id+2m-1)*//*{MyLength表示发送缓冲区地址；*//*发送元素数目为1;*//*MyID是消息标签}*//*在下面添加一条语句发送长度*/MPI_Send(&MyLength,1,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);/*若缓冲区不空，则第id+2m-1号处理器取数据的首址是data[r+1]*/if(MyLength!=0)/*在下面添加一条语句*/MPI_Send(data+r+1,MyLength,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);}/*处理器id+exp2(m-1)接受处理器id发送的消息*/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(Mallocmemoryerror!);/*在下面添加一条语句*/MPI_Recv(tmp,MyLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);}}/*递归调用并行排序，对应于算法步骤(1.4，1.5)*//*用2^m-1个处理器对start--(r-1)的数据进