MPI并行编程系列二快速排序

MPI并行编程系列二快速排序

阅读：63评论：0作者：飞得更高发表于2010-04-06 09：00原文链接在上一篇中对枚举排序的MPI并行算法进行了详细的描述和实现，算法相对简单，采用了并行编程模式中的单程序多数据流的并行编程模式。在本篇中，将对快速排序进行并行化分析和实现。本篇代码用到了上篇中的几个公用方法，在本篇中将不再做说明。

在本篇中，我们首先对快速排序算法进行描述和实现，并在此基础上分析此算法的并行性，确定并行编程模式，最后给出该算法的MPI实现。

一、快速排序算法说明

快速排序时一种最基本的排序算法，效率相对较高。其基本思想是：在当前无序数组R[1,n]中选取一个记录作为比较的"基准"，即作为排序中的"轴"。经过一趟排序后，当前无序数组R[1,n]就会以这个轴为核心划分为两个无序的子区r1[1,i-1],r2[i,n]。其中左边的无序子区都会比"轴"小，右边的无序子区都会比"轴"大。这样下一趟排序，我们就可以对这两个子区用同样的方法进行划分排序，知道所有的无序子区中的记录均排好为止。

根据算法的说明，快速排序时一个典型的递归算法，算法描述如下：

无序数组R[1],R[2],.,R[n]

quick_sort(R,start,end)

if(start end)

r=partion(R,start,end)

quick_sort(R,start,r-1)

quick_sort(R,r+1,end)

endif end quick_sort方法partion的作用就是选取"轴"，并将数组分为两个无序子区，并将该"轴"的最终位置返回，在这里我们选择数组的第一个元素为"轴"，其算法描述为：

partion(R,start,end)

r=R[start]

while(start end)

while((R[end]=r)&&(start end))

end--

end ehile R[start]=R[end]

while((R[start]r)&&(start end))

start++

end wile R[end]=R[start]

end while R[start]=r return start end partion该排序算法的性能好坏主要取决于"轴"的选定，即无序数组的划分是否均衡。最好的情况下，无序数组每次都会被划为两个均等的无序子区，这是算法的负责度为o(nlogn)；最坏的情况，无序数组每次划分都是左边n-1个元素，右边0个元素，这时算法的复杂度为o(n^2)。在通常的情况下，该算法的复杂度会依然保持在

o(nlogn)，上只不过具有更高的常数因子。因此，选定一个有效地"轴"，成为该算法的关键。一般情况下，会选定无序数组的第一个，中间或者是最后一个元素作为算法的"轴"，我们可以对着三个元素进行比较，取大小居中的那个元素作为该算法的"轴"。

二、快速排序算法的串行实现

快速排序很明显的是一个递归的程序。编写递归程序一个很重的要点就是确定在什么条件下终止递归操作。主函数代码如下：

1：void quick_sort_function(int*array,int start,int last){2：3：int part_position；4：5：if(start=last)6：return；7：8：

part_position=part_array_head(array,start,last)；9：

quick_sort_function(array,start,part_position-1)；10：

quick_sort_function(array,part_position+1,last)；11：}主函数代码很简单，一个终止递归的条件，一个递归方式。在主函数中，核心函数为

part_array_head,其代码如下：1：int part_array_head(int*array,int start,int last){2：3：int position_value=array[start]；4：5：

while(start last){6：while(start

last&&array[last]=position_value)7：last--；8：

array[start]=array[last]；9：10：while(start

last&&array[start]=position_value)11：start++；12：

array[last]=array[start]；13：}14：15：array[start]=position_value；16：17：return start；18：}从代码可以看出，快速排序的代码相对姜丹，