并行计算中快速排序算法的改进

并行计算中快速排序算法的改进摘要：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序是计算机科学中最重要的研究问题之一。本文先从串行的快速排序讲起，进而过渡到并行的快速排序算法。串行算法的平均时间复杂为O(nlogn)，而并行算法的平均时间复杂度为O(2logn)，。但是当数据量非常大的时候，传统的快速排序办法理论可行，但实际上却是不可行的。为此，本文提出一种结合归并排序的方法给出一种改进的并行快速排序，得到一个可以用在待排序的数据个数巨大时的实用的并行算法。关键词：快速排序；归并排序；串行算法；并行算法；时间复杂度1.引言排序是计算机科学中最重要的研究问题之一。由于它的应用广泛和固有的理论上的重要性，2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一[1]。因此对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛应用[2]。基本的排序问题是重排一个给定的数据项集，使它按递增（或递减）排列。数据项可以是具有线性顺序的任意对象。例如，在典型商业数据处理应用中数据项是记录，每一个记录都包含有一个称为关键字的特殊标识符域，并且记录是按关键字进行排序。排序能够大大简化查找或更新一个记录的过程。到目前为止，尽管研究人员已经设计了多种排序算法。但快速排序仍然是实际应用中最常用的一种排序算法。对它复杂度的分析方法和数据结构的研究是研究许多应用问题的基础。快速排序中使用的分治策略是设计有效计算几何和组合问题算法的典型设计方法。本文将探讨并行计算中快速排序的改进。2.快速排序简介快速排序(Quicksort)［3］是对冒泡排序的一种改进。由C．A．R．Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法是利用分治技术的典型例子。分治策略分为三步。首先将问题分成若干大小基本相等的子问题；独立地解决这些子问题；最后将子问题归并成原问题的解。因此方法的有效性取决于对初始问题划分的过程和最后一步归并解的过程。假设待排序的n个元素存储在数组A[0,n-1]中。快速排序算法的高级描述如下：(1)从数组A[0,n-1]中选取枢轴元素。(2)重排数组A中元素，并将其划分成左右两部分。使得数组中所有比枢轴元素小的元素在左部分中，比它大的元素在右部分中。(3)对左、右部分进行递归排序。如果先不看实现的细节和算法的正确性证明，不难看出算法使用了分治策略。在这种情况下，第一、二步相应于划分步，第三步求解归约的子问题，实现对整个数组的排序，从而无需归并步骤。在快速排序算法的描述中，忽视了两个关键的问题：(1)选择枢轴元素的方法；(2)如枢轴元素被选择后，使用的划分方法。2由于本文主要探讨快速算法的并行化，故采用简化的方法，直接选取数组的首个元素为枢轴元素。3.归并排序简介归并排序[4]（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序具体工作原理如下(假设序列共有n个元素):(1)将序列每相邻两个数字进行归并操作(merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素;(2)将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素;(3)重复步骤(2)，直到所有元素排序完毕。4.并行算法中的快速排序并行计算是实现高性能计算的主要技术手段[5]，排序问题是计算机科学中最重要的研究问题之一。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。尽管在最坏情况下，它的平均情况下的时间复杂度相当好[6]。将串行的快速排序并行化，必然能够提高对数据处理的效率。4.1PRAM－CRCW上快速排序算法执行快排序可以看成是构造一棵二叉树，其中主元是根，小于等于主元的元素处于左子树，大于主元的元素处于右子树。算法首先从选第一个主元开始，它划分原序列为两个自序列；然后相继子序列中主元的选取则可并行执行。当这样的二叉树造好后，采用中序遍历的方法就可得到一个有序序列[7]。令待排序的序列为(A1,…,An)，处理器Pi保存元素Ai，LC［1:n］和RC［1:n］分别记录给定主元的左孩子和右孩子，fi中存有其元素是主元的处理器号。开始时所有处理器均将它们自己的处理器号写入变量root，Aroot是第一个主元，并且root被复制给每个处理器i的fi，然后那些其元素小于Afi的处理器将其号码写入LCfi，而大于Afi的处理器将其号码写入RCfi。因此所有那些其元素属于小序列的处理器便将其号码写入LCfi，而所有那些其元素属于大于序列的处理器便将其号码写入RCfi。但是因为并发写操作只有两个值(一个对应与LCfi，另一个对应与RCfi)能被写进这些单元，所以这两个值就变成了下次迭代所需要的主元的处理器号。按此算法一直继续到n个主元被选完。4.2PRAM－CRCW上快速排序二叉树构造算法算法一：PRAM－CRCW上快速排序二叉树构造算法输入：序列（A1,…,An）和n个处理器输出：供排序用的一棵二叉排序树Begin(1)foreachprocepporido(1.1)root=i(1.2)fi=root(1.2)LCi=RCi=n+1endfor(2)repeatforeachprocepporirootdoif(AiAfi)∪(Ai=Afi∩ifi)then(2.1)LCfi=i(2.2)ifi=LCfithenexitelseif=LCfiendifelse(2.3)RCfi=i(2.4)ifi=RCfithenexitelsefi=RCfiendifendifendrepeatEnd34.3PRAM－CRCW上的快速排序二叉树中序遍历算法算法一：PRAM－CRCW上的快速排序二叉树中序遍历算法输入：A[A1,…,An]和n个处理器，并且A[j]保存在Pi的LM中输出：二叉排序树root，LC[1…n]，RC[1…n]在PM中Begin(3)foreachPipar-do(1.1)root=i(1.2)fi=root(1.2)LCi=RCi=n+1endfor(4)repeatforeachPirootpar-doif(AiAfi)∪(Ai=Afi∩ifi)then(2.1)LCfi=i(2.2)ifi=LCfithenexitelseif=LCfiendifelse(2.3)RCfi=i(2.4)ifi=RCfithenexitelsefi=RCfiendifendifendrepeatEnd在算法1中，可在O(1)时间内构造一级树，而树的高度为O(logn)，所以算法1的时间复杂度为O(logn)。当二叉树构造好以后，采用中序遍历(算法2)就可以得到一个有序序列，中序遍历的时间复杂度为O(logn)，所以并行排序算法的时间复杂度O(2logn)，要比串行的快速排序的时间复杂度(O(nlogn))小很多。但是，在并行算法里要求处理器的个数与序列中数据的个数相同，在实际应用中不可行，所以本文提出利用数据划分方法先把n(待排序的数据个数)个数据进行分段，把n个数据分为k段，即k=n/p(p为处理器的个数)，每一段有p个元素，其次在用快排序算法的思想把每一组数据进行排序，最后在用归并排序算法把P组数据进行归并排序，这样就可以解决当n远远大于p时，快排序并行算法要求待排序数据个数与处理器台数相同但是在实际应用中不可行问题。5.归并排序与快排序相结合的改进算法该算法的基本思想是：把n个数据分为k段，即k=n/p(p为处理器的个数)，每一段有p个元素，其次在用快排序算法的思想把每一组数据进行排序，最后在用归并排序算法把P组数据进行归并排序，这样就可以解决当n远远大于p时，快排序并行算法要求待排序数据个数与处理器台数相同但是在实际应用中不可行问题[8]。输入:长度为n的无序序列，有p个处理器，把n分为n/p=k段，每段有k(p=n/k)个数据，每段数据有p(p=n/k)台处理器，每台处理器有一个数据。输出:长度为n的有序序列。Begin(1)均匀划分:并行处理器有p个处理器，n个元素划分成k(n/p=k)段，每一段有p(p=n/k)个元素，即一台处理器上有一个元素。(2)局部排序:每一段上的p个处理器对p个元素进行快速排序，得到k段有序序列，用k1，k2，k3…kk表示。第k1段处理器的编号为p11，p12，p13…．p1p；第k2段4的处理器编号为p21，p22，p23...p2p，第kk段处理器编号为pk1，pk2，pk3…．pkp，每一段的数据保存在与段号与处理器编号相同的处理器上。比如，第k1段数据就保存在第p11个处理器，第k2段数据保存在第p22个处理器上，第kk段数据保存在第pkk个处理器上。这样就有k个处理器保存了k段数据，用第一个处理器和第2个处理器进行比较排序，第三个和第四个进行比较，依次类推，在用第1和第2个处理器比较得到的有序序列和第3和第4个处理器比较得到的有序序列进行比较，最后得到一个具有个n数据的有序序列。当k刚好是2的倍数时如图1所示。当k不是2的倍数时如图2所示。End5在这里分两种情况，当k≤p时，就按照本文图2进行排序。当kp时，把k进行分组，用k/p≈s(向上取整)，每个处理器放S段数据，当S是2的倍数时，如图1进行比较，s不是2的倍数时，如图2进行比较，最后得到一个具有n个数据的有序序列。6.基于群集系统的快速排序的并行化方法工作站群集COW[9][10][11]（ClusterOfWorkstations）又称工作站网络或PC群集（PCCluster）是实现并行计算的一种新的主流技术#是一种并行或分布处理系统。它是基于消息传递的、分布式存储的NIMD并行计算机结构，由一组互连的单机组成，可分为计算机节点和互连网络两部分。MPI（MessagePassingInterface）[12][13]是消息传递并行编程模型的标准，它具有可移植性、易用性、完备的异步通信功能、正式详细的精确定义等特点&。基于MPI编程就是用标准串行语言（C语言或者Fortran语言）书写的代码，加上用于消息接受和发送的库函数调用组成的，其计算其实是由一个或多个彼此通过调用库函数进行消息收、发的进程所组成。最简单的并行化方法是以一个进程为开始，根据选取的枢轴把该进程划分成两个进程，选取新的枢轴，用递归的方法把待排序列划分给若干进程，形成二叉树。每个进程由一个节点负责排序，然后最终把结果返回到主节点#从而完成整个数列的排序。伪代码如下：voidmain(intargc,char**argv{MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);MPI_comm_size(MPI_COMM_WORLD,&p);randsort();sort(0,total-1,p,0);if(my_rank==0){flag=1;for(i=0;ip;i++)MPI_Send(&flag,1,MPI_INT,i,ng,MPI_COMM_WORLD);}elseMPI_Recv(&flag,1,MPI_INT,0,ng,MPI_COMM_WORLD,&status);}MPI_Finalize();}7.总结和展望并行快速排序是一种典型的并行排序算法，但是，当待排序数据个数巨大时，在并行算法中需要N台处理器，在实际应用中不具备可行性。论文提出的算法解决了并行算法中快速排序的N值问题，但是还存在许多问题，