实验报告一快速排序并行实现_谢有军

《实验报告一快速排序并行实现_谢有军》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、—•实验目的：通过实现某种排序算法的并行化熟悉openMP的编程原理和基木编写技巧和步骤，并能了解并行算法较串行算法的优越性！二.实验内容：设计一个排序算法，并将其改成并行算法，观察串行与并行的性能差别三.实验步骤：四.3.4.1、快速排序(QuickSort)是一种最基本的排序算法,它的基本思想是:在当前无序区R[l,n]中取一个记录作为比较的“基准”(一般取第一个、最后一个或屮间位置的元素),用此基准将当前的无序区R[l,n]划分成左右两个无序的子区R[l,i-1]和R[i,n](lWiWn),H.左边

2、的无序了区中记录的所冇关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字：当R[l,i-1]和R[i,n]非空时，分别对它们重复上述的划分过程，直到所冇的无序了区中的记录均排好序为止。3.4.2、串行快速排序算法输入：无序数组data[l,n]输出：有序数组data[l,n]Begincallprocedurequicksort(data,l,n)Endprocedurequicksort(datajj)Begin(1)if(i

3、(datazizj)(1.2)quicksort(data,i,r-l);(1.3)quicksort(data,r+l,j);endifEndprocedurepartition(data,k,/)Begin(1)pivo=data[/](2)i=k-l(3)forj=kto1-1doifdata[j]Wpivotheni=i+lexchangedata[i]anddata[j]end讦endfor(4)exchangedata[i+l]anddata[/](5)returni+1End3.4.3.快速排

4、序算法的性能主要决定丁•输入数纽的划分是否均衡，而这与基准元索选择密切相关。在最坏的情况下，划分的结果是一边冇n-1个元素，而另一边冇0个索(除去被选中的基准元素)。如果每次递归排序屮的划分都产生这种极度的不平衡，么整个算法的复杂度将是矽52)。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复朵度为0(2妙)。在一般的情况下该算法仍能保持OWogn)的复杂度，只不过其具有更高的常数因子。3.4.4、快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个线程完成递归排序

5、。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个线程分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个线程处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的H的，那么排序的效率会相对较差。快速排序并行算法：输入：无序数组Data[l,n]输出：有序数组Data[l,n]BeginQuickSort_parallel(Data,0,N-l);EndProcedurepara_quicksort(Data,OzN-l)Beg

6、inif(Begin#inc

7、lude#include#includeintPartition(int*data,intstart,intend){intpivo;inti,j;inttmp;pivo=data[end];i=start-l;/*i(活动指针)*/for(j=start;j

8、];data[i+l]=data[end];data[end]=tmp;/*以pivo为分界，data[i+l]=pivo*/returni;}int*QuickSort_parallel(int*DatajntBeginjntEnd){intr;if(Begin