实验二 快速排序的MPI并行程序
（一）实验时间： 2015年11月5日 （二）实验名称： 快速排序的mpi并行化设计 （三）内容与要求：
1、内容：快速排序（以下简称快排）是对冒泡排序的一种改进，它的思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。而此次试验要将mpi运用到快速排序中，达到并行化排序的效果。 2、要求：
（1）请使用MPI并行程序设计实现快速排序的并行化；
（2）正文格式：宋体，小四，首行缩进两字符，单倍行距，两端对齐
（四）实验步骤
1.运行mpi环境 2.初始化一个数组 3.定义m=log2N，然后2m为程序确定进程个数的个数，N是指整个程序调用的进程数。
4.将数组中的数据依照快排的方式划分成2m份，然后发送给各个进程 5．各进程按串行快排，并将结果按层次返回给跟进程
（五）关键代码实现（只写出关键代码）
void MpiQs(int *a,int left,int right,int m,int id,int myid){ int *temp;//定义的接收数组信息的存储位置 int leftSize,rightSize; MPI_Status status; //如果进程分完则串行快排 if(m==0){ if(id==myid) {quikSort(a,left,right);} return; } //给下个进程分发数据位置
int mid; if(id==myid){ mid=order_qs(a,left,right); rightSize=right-mid; leftSize=mid-left; //printf(\对下个进程发送进程号:%d l:%d r%d\\n\
MPI_Send(&rightSize,1,MPI_INT,id+exp2(m-1),myid,MPI_COMM_WORLD);
//MPI_Recv(&rightSize,1,MPI_INT,id+exp2(m-1),id,MPI_COMM_WORLD,&status); //printf(\排序中 发送排序个数 the procs:%d\\n\ if(rightSize!=0){
MPI_Send(a+mid+1,rightSize,MPI_INT,id+exp2(m-1),myid,MPI_COMM_WORLD); // printf(\排序中 发送数据 the procs:%d\\n\ } } //对上个进程数据的接收 if(myid==id+exp2(m-1)){ //printf(\对上个进程接收进程号:%d l:%d r%d\\n\
MPI_Recv(&rightSize,1,MPI_INT,id,id,MPI_COMM_WORLD,&status); //printf(\排序中 接收排序个数 the procs:%d\\n\ if(rightSize!=0){ temp=(int *)malloc(rightSize*sizeof(int)); if(temp==0)printf(\申请临时数组内存出错\
//MPI_Recv(temp,67,MPI_INT,id,id,MPI_COMM_WORLD,&status);
MPI_Recv(temp,rightSize,MPI_INT,id,id,MPI_COMM_WORLD,&status); // printf(\排序中 接收数据 the procs:%d\\n\ } } //快排递归 MPI_Bcast(&leftSize,1,MPI_INT,id,MPI_COMM_WORLD); if(leftSize>0){//printf(\递归中\\n\MpiQs(a,left,mid-1,m-1,id,myid);} MPI_Bcast(&rightSize,1,MPI_INT,id,MPI_COMM_WORLD); if(rightSize>0){//printf(\递归中\\n\
MpiQs(temp,0,rightSize-1,m-1,id+exp2(m-1),myid);}
//发送与接收数据 if((myid==id+exp2(m-1))&&(rightSize!=0)){
MPI_Send(temp,rightSize,MPI_INT,id,id+exp2(m-1),MPI_COMM_WORLD); //printf(\排序后 发送数据 the procs:%d\\n\ } if((myid==id)&&(rightSize!=0)){
MPI_Recv(a+mid+1,rightSize,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status); //printf(\排序后 接收数据 the procs:%d\\n\ } }
截图效果：20个进程计算 快排数组序列为100
（六）实验总结与思考
本次实验根据老师讲解步骤，自己思考了一番，似懂非懂并没有什么思路。在百度上找了一份关于快速排序实验报告和代码，仔细阅读其设计过程，和源码，了解了其设计步骤，思路。在并行化快速排序中最关键的就是处理数据的划分，及其处理各进程数据的发送及汇总。
这部分的代码是整个实验的关键。在整个实验中将并行化的思想体现的也是这个部分，这是重点也是难点，这部分通过mpi将数据发送到各个进程，以及从各个进程接收数据。