并行計算中快速排序算法的改進(共6頁)

1、并行計算中快速排序算法的改進摘要：排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。排序是計算機科學(xué)中最重要的研究問題之一。本文先從串行的快速排序講起，進而過渡到并行的快速排序算法。串行算法的平均時間復(fù)雜為O(nlogn)，而并行算法的平均時間復(fù)雜度為O(2logn)，。但是當(dāng)數(shù)據(jù)量非常大的時候，傳統(tǒng)的快速排序辦法理論可行，但實際上卻是不可行的。為此，本文提出一種結(jié)合歸并排序的方法給出一種改進的并行快速排序，得到一個可以用在待排序的數(shù)據(jù)個數(shù)巨大時的實用的并行算法。關(guān)鍵詞：快速排序；歸并排序；串行算法；并行算法；時間復(fù)雜度1. 引言排序是計算機科學(xué)中最重

2、要的研究問題之一。由于它的應(yīng)用廣泛和固有的理論上的重要性，2000年它被列為對科學(xué)和工程計算的研究與實踐影響最大的10大問題之一1。因此對于排序的研究既有理論上的重要意義，又有實際應(yīng)用價值。它在計算機圖形、計算機輔助設(shè)計、機器人、模式識別及統(tǒng)計學(xué)等領(lǐng)域具有廣泛應(yīng)用2?；镜呐判騿栴}是重排一個給定的數(shù)據(jù)項集，使它按遞增（或遞減）排列。數(shù)據(jù)項可以是具有線性順序的任意對象。例如，在典型商業(yè)數(shù)據(jù)處理應(yīng)用中數(shù)據(jù)項是記錄，每一個記錄都包含有一個稱為關(guān)鍵字的特殊標識符域，并且記錄是按關(guān)鍵字進行排序。排序能夠大大簡化查找或更新一個記錄的過程。到目前為止，盡管研究人員已經(jīng)設(shè)計了多種排序算法。但快速排序仍然是實際

3、應(yīng)用中最常用的一種排序算法。對它復(fù)雜度的分析方法和數(shù)據(jù)結(jié)構(gòu)的研究是研究許多應(yīng)用問題的基礎(chǔ)?？焖倥判蛑惺褂玫姆种尾呗允窃O(shè)計有效計算幾何和組合問題算法的典型設(shè)計方法。本文將探討并行計算中快速排序的改進。2. 快速排序簡介快速排序( Quicksort)3是對冒泡排序的一種改進。由C A R Hoare 在1962 年提出。它的基本思想是: 通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列?？焖倥判蛩惴ㄊ抢梅种渭夹g(shù)的典型例子。分治策略分為三步。首先將

4、問題分成若干大小基本相等的子問題；獨立地解決這些子問題；最后將子問題歸并成原問題的解。因此方法的有效性取決于對初始問題劃分的過程和最后一步歸并解的過程。假設(shè)待排序的n個元素存儲在數(shù)組A0, n-1中?？焖倥判蛩惴ǖ母呒壝枋鋈缦拢?1) 從數(shù)組A0, n-1中選取樞軸元素。(2) 重排數(shù)組A中元素，并將其劃分成左右兩部分。使得數(shù)組中所有比樞軸元素小的元素在左部分中，比它大的元素在右部分中。(3) 對左、右部分進行遞歸排序。如果先不看實現(xiàn)的細節(jié)和算法的正確性證明，不難看出算法使用了分治策略。在這種情況下，第一、二步相應(yīng)于劃分步，第三步求解歸約的子問題，實現(xiàn)對整個數(shù)組的排序，從而無需歸并步驟。在快速

5、排序算法的描述中，忽視了兩個關(guān)鍵的問題：(1) 選擇樞軸元素的方法；(2) 如樞軸元素被選擇后，使用的劃分方法。由于本文主要探討快速算法的并行化，故采用簡化的方法，直接選取數(shù)組的首個元素為樞軸元素。3. 歸并排序簡介歸并排序4（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序具體工作原理如下( 假設(shè)序列共有 n 個元素) :( 1) 將 序 列 每 相 鄰 兩 個

6、數(shù) 字 進 行 歸 并 操 作( merge) ，形成 floor( n /2) 個序列，排序后每個序列包含兩個元素;( 2) 將上述序列再次歸并，形成 floor( n /4) 個序列，每個序列包含四個元素;( 3) 重復(fù)步驟( 2) ，直到所有元素排序完畢。4. 并行算法中的快速排序并行計算是實現(xiàn)高性能計算的主要技術(shù)手段5，排序問題是計算機科學(xué)中最重要的研究問題之一。對快速排序方法的研究表明，至今快速排序算法仍然是流傳久遠的最實用的排序算法。盡管在最壞情況下，它的平均情況下的時間復(fù)雜度相當(dāng)好6。將串行的快速排序并行化，必然能夠提高對數(shù)據(jù)處理的效率。4.1 PRAMCRCW 上快速排序算法執(zhí)

7、行快排序可以看成是構(gòu)造一棵二叉樹，其中主元是根，小于等于主元的元素處于左子樹，大于主元的元素處于右子樹。算法首先從選第一個主元開始，它劃分原序列為兩個自序列；然后相繼子序列中主元的選取則可并行執(zhí)行。當(dāng)這樣的二叉樹造好后，采用中序遍歷的方法就可得到一個有序序列7。令待排序的序列為( A1, , An) ，處理器 Pi 保存元素 Ai，LC1: n和 RC1: n分別記錄給定主元的左孩子和右孩子，fi 中存有其元素是主元的處理器號。開始時所有處理器均將它們自己的處理器號寫入變量root，Aroot 是第一個主元，并且 root 被復(fù)制給每個處理器i的 fi，然后那些其元素小于 Afi 的處理器將其

8、號碼寫入LCfi，而大于Afi的處理器將其號碼寫入RCfi。因此所有那些其元素屬于小序列的處理器便將其號碼寫入LCfi，而所有那些其元素屬于大于序列的處理器便將其號碼寫入 RCfi。但是因為并發(fā)寫操作只有兩個值( 一個對應(yīng)與 LCfi，另一個對應(yīng)與 RCfi) 能被寫進這些單元，所以這兩個值就變成了下次迭代所需要的主元的處理器號。按此算法一直繼續(xù)到 n 個主元被選完。4.2 PRAMCRCW 上快速排序二叉樹構(gòu)造算法算法一：PRAMCRCW 上快速排序二叉樹構(gòu)造算法輸入：序列（A1, , An）和n個處理器輸出：供排序用的一棵二叉排序樹Begin(1) for each proceppor i

9、 do(1.1) root = i(1.2) fi = root(1.2) LCi = RCi = n + 1endfor(2) repeat for each proceppor i < > root doif (Ai < Afi) (Ai = Afi i < fi) then (2.1) LCfi = i(2.2) if i = LCfi then exit else if = LCfi endifelse(2.3) RCfi = i(2.4) if i = RCfi then exit else fi = RCfi endifendifend repeatEnd4

10、.3 PRAMCRCW 上的快速排序二叉樹中序遍歷算法算法一：PRAMCRCW 上的快速排序二叉樹中序遍歷算法輸入：AA1, , An和n個處理器，并且Aj保存在Pi的LM中輸出：二叉排序樹root，LC1n，RC1n在PM中Begin(3) for each Pi par-do(1.1) root = i(1.2) fi = root(1.2) LCi = RCi = n + 1endfor(4) repeat for each Pi < > root par-doif (Ai < Afi) (Ai = Afi i < fi) then (2.1) LCfi = i(

11、2.2) if i = LCfi then exit else if = LCfi endifelse(2.3) RCfi = i(2.4) if i = RCfi then exit else fi = RCfi endifendifend repeatEnd在算法1 中，可在O( 1) 時間內(nèi)構(gòu)造一級樹，而樹的高度為O( logn) ，所以算法1 的時間復(fù)雜度為O( logn) 。當(dāng)二叉樹構(gòu)造好以后，采用中序遍歷( 算法2) 就可以得到一個有序序列，中序遍歷的時間復(fù)雜度為O( logn)，所以并行排序算法的時間復(fù)雜度O( 2logn) ，要比串行的快速排序的時間復(fù)雜度( O( nlogn)

12、 ) 小很多。但是，在并行算法里要求處理器的個數(shù)與序列中數(shù)據(jù)的個數(shù)相同，在實際應(yīng)用中不可行，所以本文提出利用數(shù)據(jù)劃分方法先把n( 待排序的數(shù)據(jù)個數(shù)) 個數(shù)據(jù)進行分段，把n 個數(shù)據(jù)分為k 段，即k= n /p( p 為處理器的個數(shù)) ，每一段有p 個元素，其次在用快排序算法的思想把每一組數(shù)據(jù)進行排序，最后在用歸并排序算法把P 組數(shù)據(jù)進行歸并排序，這樣就可以解決當(dāng)n遠遠大于p 時，快排序并行算法要求待排序數(shù)據(jù)個數(shù)與處理器臺數(shù)相同但是在實際應(yīng)用中不可行問題。5. 歸并排序與快排序相結(jié)合的改進算法該算法的基本思想是：把n 個數(shù)據(jù)分為k 段，即k= n /p( p 為處理器的個數(shù)) ，每一段有p 個元素

13、，其次在用快排序算法的思想把每一組數(shù)據(jù)進行排序，最后在用歸并排序算法把P 組數(shù)據(jù)進行歸并排序，這樣就可以解決當(dāng)n遠遠大于p 時，快排序并行算法要求待排序數(shù)據(jù)個數(shù)與處理器臺數(shù)相同但是在實際應(yīng)用中不可行問題8。輸入 : 長度為 n 的無序序列，有 p 個處理器，把 n 分為 n /p = k 段，每段有 k( p = n /k) 個數(shù)據(jù)，每段數(shù)據(jù)有 p( p = n /k) 臺處理器，每臺處理器有一個數(shù)據(jù)。輸出: 長度為 n 的有序序列。Begin( 1) 均勻劃分: 并行處理器有 p 個處理器，n 個元素劃分成 k( n /p = k) 段，每一段有 p( p = n /k) 個元素，即一臺處理

14、器上有一個元素。( 2) 局部排序: 每一段上的 p 個處理器對 p 個元素進行快速排序，得到 k 段有序序列，用 k1，k2，k3kk 表示。第 k1 段處理器的編號為 p11，p12，p13 p1p； 第 k2 段的處理器編號為 p21，p22，p23 . p2p，第kk 段處理器編號為 pk1，pk2，pk3 pkp，每一段的數(shù)據(jù)保存在與段號與處理器編號相同的處理器上。比如，第 k1 段數(shù)據(jù)就保存在第 p11 個處理器，第 k2 段數(shù)據(jù)保存在第 p22 個處理器上，第 kk 段數(shù)據(jù)保存在第pkk 個處理器上。這樣就有 k 個處理器保存了 k 段數(shù)據(jù)，用第一個處理器和第 2 個處理器進行比

15、較排序，第三個和第四個進行比較，依次類推，在用第 1 和第 2 個處理器比較得到的有序序列和第 3 和第 4 個處理器比較得到的有序序列進行比較，最后得到一個具有個 n數(shù)據(jù)的有序序列。當(dāng) k 剛好是 2 的倍數(shù)時如圖 1 所示。當(dāng) k 不是 2 的倍數(shù)時如圖 2 所示。End在這里分兩種情況，當(dāng)kp時，就按照本文圖2進行排序。當(dāng)k>p時，把k 進行分組，用k /p s (向上取整) ，每個處理器放S 段數(shù)據(jù)，當(dāng)S是2的倍數(shù)時，如圖1進行比較，s不是2的倍數(shù)時，如圖2進行比較，最后得到一個具有n個數(shù)據(jù)的有序序列。6. 基于群集系統(tǒng)的快速排序的并行化方法工作站群集COW91011（Clust

16、er Of Workstations）又稱工作站網(wǎng)絡(luò)或PC群集（PC Cluster）是實現(xiàn)并行計算的一種新的主流技術(shù)#是一種并行或分布處理系統(tǒng)。它是基于消息傳遞的、分布式存儲的NIMD并行計算機結(jié)構(gòu)，由一組互連的單機組成，可分為計算機節(jié)點和互連網(wǎng)絡(luò)兩部分。MPI（Message Passing Interface）1213是消息傳遞并行編程模型的標準，它具有可移植性、易用性、完備的異步通信功能、正式詳細的精確定義等特點&?；贛PI編程就是用標準串行語言（C語言或者Fortran語言）書寫的代碼，加上用于消息接受和發(fā)送的庫函數(shù)調(diào)用組成的，其計算其實是由一個或多個彼此通過調(diào)用庫函數(shù)進行

17、消息收、發(fā)的進程所組成。最簡單的并行化方法是以一個進程為開始，根據(jù)選取的樞軸把該進程劃分成兩個進程，選取新的樞軸，用遞歸的方法把待排序列劃分給若干進程，形成二叉樹。每個進程由一個節(jié)點負責(zé)排序，然后最終把結(jié)果返回到主節(jié)點#從而完成整個數(shù)列的排序。偽代碼如下：void main (int argc, char *argvMPI_Init(&argc, &argv);MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);MPI_comm_size(MPI_COMM_WORLD, &p);randsort();sort(0, total-1,

18、p, 0);if(my_rank = 0) flag = 1; for(i = 0; i < p; i+) MPI_Send(&flag, 1, MPI_INT, i, ng, MPI_COMM_WORLD);else MPI_Recv(&flag, 1, MPI_INT, 0, ng, MPI_COMM_WORLD, &status);MPI_Finalize(); 7. 總結(jié)和展望并行快速排序是一種典型的并行排序算法，但是，當(dāng)待排序數(shù)據(jù)個數(shù)巨大時，在并行算法中需要N 臺處理器，在實際應(yīng)用中不具備可行性。論文提出的算法解決了并行算法中快速排序的N值問題，但是還存在許多問題，希望通過補充更多的算例，豐富、完善乃至開拓出更新更好的方法。參考文獻：1 J Dongarra. The Top 100 Algorithms. IEEE Computing in Science & Engineering, 2000, 2(1):22-23.2 T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction to Algorithms. MIT Press, September