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、快速排序（Quick Sort）是一种最基本的排序算法，它的基本思想是：在当前无序区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] Begin call procedure quicksort(data,1,n) End
procedure quicksort(data,i,j) Begin
(1) if (i (1.1)r = partition(data,i,j) (1.2)quicksort(data,i,r-1); (1.3)quicksort(data,r+1,j); end if End procedure partition(data,k,l) Begin (1) pivo=data[l] (2) i=k-1 (3) for j=k to l-1 do if data[j]≤pivo then i=i+1 exchange data[i] and data[j] end if end for (4) exchange data[i+1] and data[l] (5) return i+1 End 3.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] Begin para_quicksort(data,1,n,m,0) End procedure para_quicksort(data,i,j,m,id) Begin (1) if (j-i)≤k or m=0 then (1.1) Pid call quicksort(data,i,j) else (1.2) Pid: r=patrition(data,i,j) (1.3) P id send data[r+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 data[r+1,m-1] back to Pid end if End 3.4.6、在最优的情况下该并行算法形成一个高度为logn的排序树，其计算复杂度为O（n），通信复杂度也为O（n）。同串行算法一样，在最坏情况下其计算复杂度降为O（n2）。正常情况下该算法的计算复杂度也为O（n），只不过具有更高的常数因子。 3.4.7、完成快速排序的并行实现的流程图 初始化 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号处理器划分数据，并将后一部分数据发送到处理器id+exp2(m-1) (1.2) Pid: r=patrition(data,i,j) r=Partition(data,start,end); (1.3)Pid send data[r+1,end] to P(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); 处理器id+exp2(m-1)接受处理器id发送的消息 递归调用并行排序 用2^m-1个处理器对start--(r-1)的数据进行递归排序 用2^m-1个处理器对(r+1)--end的数据进行递归排序 将排序好的数据由处理器id+exp2(m-1)发回id号处理器 ID号为0的处理器打印排序完的有序序列 3.4.8、完成快速排序的并行算法的实现 #include * 函数名: main * 功能：实现快速排序的主程序 * 输入：argc为命令行参数个数； * argv为每个命令行参数组成的字符串数组。 * 输出：返回0代表程序正常结束