[科普中國(guó)]-并行排序

并行排序算法，是計(jì)算機(jī)并行計(jì)算能力大大發(fā)展之后，為了提高排序效率而提出的算法。

串行算法直接并行化1模擬快速排序

超立方體網(wǎng)絡(luò)是基于超立方體連接構(gòu)建的網(wǎng)絡(luò)。網(wǎng)絡(luò)中以格雷碼對(duì)各頂點(diǎn)編號(hào)。在下面的描述中，設(shè)頂數(shù)，待排序元素共有n個(gè)。

超立方體上的快速排序是這樣進(jìn)行的：首先我們將n個(gè)元素分配到p個(gè)處理器上，為了使問(wèn)題討論簡(jiǎn)單化，假設(shè)n是p的整數(shù)倍，那么每個(gè)頂點(diǎn)將會(huì)分到個(gè)元素。然后隨機(jī)選一個(gè)主元，各個(gè)處理器將每個(gè)頂點(diǎn)中的元素按與主元的比較結(jié)果分為兩部分。這個(gè)算法的關(guān)鍵點(diǎn)在這里，對(duì)每一個(gè)處理器（頂點(diǎn)）在進(jìn)行第i次劃分時(shí)，將大于主元的部分都送到超立方體的一個(gè)d-i維自立方體中，而將小于主元的部分送到另一個(gè)d-i位的子立方體中，這樣就模擬了快速排序中的劃分算法。子立方體可以這樣選擇：在第i次劃分中判斷第i位是0還是1。劃分算法到處理完所有1維子立方體后結(jié)束。接下來(lái)對(duì)每個(gè)頂點(diǎn)中的元素調(diào)用串行算法進(jìn)行局部排序，最后對(duì)整個(gè)立方體進(jìn)行一次遍歷便可得到排好序的元素。

由快速排序的過(guò)程，我們可以看到，快速排序?qū)嶋H上就是在構(gòu)造一棵二叉樹，讓劃分主元位于根節(jié)點(diǎn)，使得左子節(jié)點(diǎn)小于或等于根而右子節(jié)點(diǎn)大于根，最后對(duì)整棵二叉樹進(jìn)行一次中序遍歷，便可以得到最后排好序的數(shù)列。

我們可以選n個(gè)處理器分別保存待排序數(shù)組A的n個(gè)元素，處理器對(duì)應(yīng)一個(gè)變量用于存放主元元素的處理器號(hào)，以及兩個(gè)變量L,R分別存放其左右兒子。開始時(shí)，每一個(gè)處理器都試圖往變量root中寫入它的處理器號(hào)，若果我們使用PRAM-CRCW計(jì)算模型，那么就只有一個(gè)能夠?qū)懭雛oot，接著root被復(fù)制給每一個(gè)處理器的。然后對(duì)于每個(gè)處理器（除去被原為主元的那個(gè)外）判斷其值與的大小，從而確定放入還是，同樣的，由于并發(fā)操作的互斥性，只有一個(gè)只能被最終寫入，他們就作為下次劃分的主元。算法繼續(xù)進(jìn)行直到n個(gè)主元被選完為止。

串行算法簡(jiǎn)介：快速排序是一種較為高效的排序算法，它通過(guò)不斷的劃分待排序列為兩段，使得前一段總小于或等于某個(gè)數(shù)，而后一段總大于某個(gè)數(shù)，這樣每次劃分就能確定一個(gè)數(shù)的最終位置。一般情況下，如果每次劃分的兩個(gè)子列大致等長(zhǎng)，那么它的時(shí)間復(fù)雜度是。

2.在PRAM-CRCW計(jì)算模型上利用二叉樹網(wǎng)絡(luò)模擬快速排序

時(shí)間復(fù)雜度分析：由于一層節(jié)點(diǎn)的構(gòu)造時(shí)間是，所以算法的時(shí)間復(fù)雜度是

二叉樹上模擬快速排序

超立方體上模擬快速排序

比較器網(wǎng)絡(luò)上的并行排序比較器網(wǎng)絡(luò)一般是指由Batcher比較器構(gòu)成的網(wǎng)絡(luò)。這些比較器均可以執(zhí)行兩個(gè)數(shù)之間的比較與條件交換(CCI)操作。Batcher排序網(wǎng)絡(luò)是由一系列Batcher歸并網(wǎng)絡(luò)組成的，故Batcher排序網(wǎng)絡(luò)可以分為奇偶排序網(wǎng)絡(luò)和雙調(diào)排序網(wǎng)絡(luò)兩大類。

高德納(Knuth)的0-1原理

奇偶排序網(wǎng)絡(luò)(Odd-Even Sorting Network)

雙調(diào)排序網(wǎng)絡(luò)(Bitonic Sorting Network)2

本詞條內(nèi)容貢獻(xiàn)者為:

李航 - 副教授 - 西南大學(xué)