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

《并行计算中快速排序算法的改进》由会员分享，可在线阅读，更多相关《并行计算中快速排序算法的改进（6页珍藏版）》请在装配图网上搜索。

1、并行计算中快速排序算法的改进摘要：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列 调整为“有序”的记录序列。排序是计算机科学中最重要的研究问题之一。本文先 从串行的快速排序讲起，进而过渡到并行的快速排序算法。串行算法的平均时间复 杂为O(nlogn),而并行算法的平均时间复杂度为0(21ogn),。但是当数据量非常大 的时候，传统的快速排序办法理论可行，但实际上却是不可行的。为此，本文提出 一种结合归并排序的方法给出一种改进的并行快速排序，得到一个可以用在待排序 的数据个数巨大时的实用的并行算法。关键词：快速排序；归并排序；串行算法；并行算法；时间复杂度1 .引言排序是计算

2、机科学中最重要的研究问题之一。由于它的应用广泛和同行的理论上的重要 性，2000年它被列为对科学和工程计算的研窕与实践影响最大的10大问题之一口】。因此对 干排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设 汁、机器人、模式识别及统计学等领域具有广泛应用基本的排序问题是重排一个给定的 数据项集，使它按递增(或递减)排列。数据项可以是具有线性顺序的任意对象。例如，在 典型商业数据处理应用中数据项是记录，每一个记录都包含有一个称为关键字的特殊标识符 域，并且记录是按关键字进行排序。排序能够大大简化查找或更新一个记录的过程。到目前 为止，尽管研究人员已经设计了多种排序算

3、法。但快速排序仍然是实际应用中最常用的一种 排序算法。对它复杂度的分析方法和数据结构的研究是研究许多应用问题的基础。快速排序 中使用的分治策略是设计布.效计算几何和组合问题算法的典型设计方法。本文将探讨并行计 算中快速排序的改进。2 .快速排序简介快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年 提出。它的基本思想是通过-趟排序将要排序的数据分割成独立的两部分，其中一部分的 所有数据都比另外一部分的所行数据都要小，然后再按此方法时这两部分数据分别进行快速 排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法是利用分治技术的典

4、型例子。分治策略分为三步。首先将问题分成若干大 小基本相等的子问题；独立地解决这些子问题；最后将子问题归并成原问题的解。因此方法 的有效性取决于对初始问题划分的过程和最后一步归并解的过程。假设待排序的n个元素存储在数组A0,n-l中。快速排序算法的高级描述如下：(1)从数组A0,n-l中选取枢轴元素。(2)重排数组A中元素，并将其划分成左右两部分。使得数组中所有比枢轴元索小的元 素在左部分中，比它大的元素在右部分中。(3)对左、右部分进行递归排序。如果先不看实现的细节和算法的正确性证明，不难看出算法使用了分治策略。在这种情 况卜:第一、二步相应于划分步，第三步求解归约的子问题，实现对整个数组的

5、排序，从而 无需归并步骤。在快速排序算法的描述中，忽视了两个关键的问题：(1)选择枢轴元素的方法；(2)如枢轴元素被选择后，使用的划分方法。由于本文主要探讨快速算法的并行化，故采用简化的方法，直接选取数组的首个元素为 枢轴元素。3 .归并排序艮一归并排序内(MERGESORT)是建立在此并操作上的一种有效的排序算法，该算法是采 用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列公井，得到完 全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个 有序表，称为二路归并。归并排序具体工作原理如下(假设序列共有n个元素)：(1)将序列每相

6、邻两个数字进行归并操作(merge),形成floor(n/2)个序列，排序后每 个序列包含两个元素，(2)将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素，(3)重复步骤(2),直到所有元素排序完毕。4 .并行算法中的快速排序并行计算是实现高性能计算的主要技术手段叫排序问题是计算机科学中最重要的研究 问题之一。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序 算法。尽管在最坏情况它的平均情况卜的时间复杂度相当好巴 将串行的快速排序并行 化，必然能够提高对数据处理的效率。4.1 PRAM-CRCW上快速排序算法执行快排序可以看成是构造一棵二叉树，其中

7、主元是根，小于等于主元的元素处于左子 树，大于主元的元素处于右子树。算法首先从选第一个主元开始，它划分原序列为两个自序 列：然后相继子序列中主元的选取则可并行执行。当这样的二叉树造好后，采用中序遍历的 方法就可得到一个有序序列田。令待排序的序列为(A1,，An),处理器Pi保存元素Ai, LC i n和RC l:n 分别记录给定主元的左孩子和右孩子，fi中存有其元素是主元的处理器号。开始时所有处 理器均将它们自己的处理器号写入变量root, Aroot是第一个主元，并且root被复制给每 个处理器1的fi.然后那些其元素小于Afi的处理器将其号码写入LCH,而大于Afi的处理 器将其号码写入R

8、Cfi。因此所有那些其元索属于小序列的处理器便将其号码写入LCfi,而 所有那些其元素屈于大于序列的处理器便将其号码写入RCfi。但是闪为并发写操作只有两 个做一个对应与LCfi,另一个对应与RCfi)能被写进这些单元，所以这两个值就变成了下 次迭代所需要的主元的处理器号。按此算法一直继续到n个主元被选完。4.2 PRAM-CRCW上快速排序二叉树构造算法算法一：PRAM-CRCW上快速排序二叉树构造算法输入：序列(Al,. ,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin(1) fbr each proceppori do(l.(1) ot = i(l.(2) fi = ro

9、ot(1.(2) i = RCi = n+ 1endfor(2) repeat for each proceppono root do if (Ai Afi) U (Ai = Afi A i fi) then(2 l)LCfi = i(2 2) if i = LCfi then exit else if = LCfi end:felse(2 3) RCfi = i(2 4) if i = RCfi then exit else ft = RCfi end:fend:fend repeatEnd4.3 PRAM-CRCW上的快速排序二叉树中序遍历算法尊法一：PRAM-CRCW上的快速排序二叉树中

10、序遍历算法 输入：AA1,，An和n个处理器，并且Aj保存在Pi的LM中 输出：二叉排序树 root, LC1 . n, RCl. n在 PM 中 Begin(3) for each Pi par-do(1.(1) ot = i(1.(2) fi = root(1.(3) i = RCi = n+ 1 endfor(4) repeat for each Pi root pai-do if (Ai Afi) U (Ai =Afi n i p时，把k进行分组， 用k/p s(向上取整)，每个处理器放S段数据，当S是2的倍数时，如图1进行比较，s 不是2的倍数时，如图2进行比较，最后得到一个具有n个

11、数据的有序序列。6 .基于群集系统的快速排序的并行化方法工作站群集cow叨0Cluster Of Workstations)又称工作站网络或PC群集(PC Cluster) 是实现并行计算的一种新的主流技术#是一种并行或分布处理系统。它是基于消息传递的、 分布式存储的NIMD并行计算机结构，由一组互连的单机组成，可分为计算机节点和互连 网络两部分。MPI (Message Passing Interface) 口加力是消息传递并行编程模型的标准，它具有可移植 性、易用性、完备的异步通信功能、正式详细的精确定义等特点及。基于MPI编程就是用 标准串行语言(C语言或者Fortran语言)书写的代码

12、，加上用于消息接受和发送的库函数 调用组成的，其计算其实是由一个或多个彼此通过调用库函数进行消息收、发的进程所组成。最简单的并行化方法是以一个进程为开始，根据选取的枢轴把该进程划分成两个进程, 选取新的枢轴，用递归的方法把待排序列划分给若干进程，形成二叉树。每个进程由一个节 点负货排序，然后最终把结果返回到主节点#从而完成整个数列的排序。伪代码如下：void main (intargc, char *argvMPI_Init(&argc, &argv),MPI_C omm_rank(MPI_CORLD, &my_rank),MPI_comm_size(NPI_COhlhI_WORLD, &p)

13、,randsortO,sort。total-1, p, 0),if(my_rank = 0)flag=l,for(i = 0, i p, i+)hlPI_Send(&flag, l,hlPI_INT, i, ng, h4PI_COMhf_WORLD),elseMPI_Recv(&flag, 1, MPI_INT, 0, ng, MPI_C0MM_W0RLD, &status),)MPI_FinalizeO；)7 .总结和展望并行快速排序是一种典型的并行排序算法，但是，当待排序数据个数巨大时，在并行算 法中需要N台处理器，在实际应用中不具备可行性。论文提出的算法解决了并行算法中快 速排序的N值问

14、题，但是还存在许多问题，希望通过补充更多的算例，丰富、完善乃至开 拓出更新更好的方法。参考文献：1 J Dongaira The Top 100 Algorithms IEEE Computing in Science & Engineering, 2000, 2(1):22-232 T H Coimen, C E Leiserson, R L Rivest Introduction to Algonthms MIT Press, September, 2001, Sorting and Order Statistics3 G-. Baudet, Asynchi-onous Iterative

15、 Methods for Multiprocessors, J ACM, 25 ( 1978): 226-2444严前敏，吴伟民.数据结构(C语言版)M清华大学出版社，2014： 283-284杨学军.并行计算六十年J计算机工程与科学,2012,(08):1-10霍红卫，许进 快速排序算法研究J微电子学与计算机,2002,(06) 6-97陈国良 并行计算结构算法编程M.北京：高等教行出版社，1999.网李跃新，周四维.并行计算中快速排序算法的改进J湖北第二师范学院学报,2011,(08): 1-3.9刘小毛.支持分布式超级计算的工作站群集系统J.小型微型计算机系 统,1995,(02) 45-5210黄伟，赖国明.基于群集系统的快速排序并行化方法J现代计算机(专业 ),2005,(05):89-91.11赖国明，杨圣云.一种利用工作站群集的并行计算研究方案J.河南大学学报(自然科学 版)二004,(02):80-8212黄伟 一种基于MPI和工作站群集的并行计算J电脑学习,2005,(01):31-3213张治宏.基于MPI的并行计算研究D.中国地质大学(北京)，2006