並行排序

並行排序算法是計算機並行計算能力大大發展之後，為了提高排序效率而提出的算法。

劃分的設計方法[編輯]

串行算法直接並行化[編輯]

模擬快速排序
- 二叉樹上模擬快速排序
  - 串行算法簡介：快速排序是一種較為高效的排序算法，它通過不斷的劃分待排序列為兩段，使得前一段總小於或等於某個數，而後一段總大於某個數，這樣每次劃分就能確定一個數的最終位置。一般情況下，如果每次劃分的兩個子列大致等長，那麼它的時間複雜度是 $O\left(n\log n\right)$ 。
  - 在PRAM-CRCW計算模型上利用二叉樹網絡模擬快速排序
    - 由快速排序的過程，我們可以看到，快速排序實際上就是在構造一棵二叉樹，讓劃分主元位於根節點，使得左子節點小於或等於根而右子節點大於根，最後對整棵二叉樹進行一次中序遍歷，便可以得到最後排好序的數列。
    - 我們可以選n個處理器分別保存待排序數組A的n個元素，處理器 $P_{i}$ 對應一個變量 $X_{i}$ 用於存放主元元素的處理器號，以及兩個變量L,R分別存放其左右兒子。開始時，每一個處理器都試圖往變量root中寫入它的處理器號，若果我們使用PRAM-CRCW計算模型，那麼就只有一個能夠寫入root，接着root被複製給每一個處理器的 $X_{i}$ 。然後對於每個處理器（除去被原為主元的那個外）判斷其值與 $A_{X_{i}}$ 的大小，從而確定放入 $L_{X_{i}}$ 還是 $R_{X_{i}}$ ，同樣的，由於並發操作的互斥性，只有一個只能被最終寫入，他們就作為下次劃分的主元。算法繼續進行直到n個主元被選完為止。
  - 時間複雜度分析：由於一層節點的構造時間是 $\Theta (1)$ ，所以算法的時間複雜度是 $\Theta (logn)$
- 超立方體上模擬快速排序
  - 超立方體網絡是基於超立方體連接構建的網絡。網絡中以格雷碼對各頂點編號。在下面的描述中，設頂點數 $p=2^{d}$ ，待排序元素共有n個。
  - 超立方體上的快速排序是這樣進行的：首先我們將n個元素分配到p個處理器上，為了使問題討論簡單化，假設n是p的整數倍，那麼每個頂點將會分到 ${\frac {n}{p}}$ 個元素。然後隨機選一個主元，各個處理器將每個頂點中的元素按與主元的比較結果分為兩部份。這個算法的關鍵點在這裡，對每一個處理器（頂點）在進行第i次劃分時，將大於主元的部分都送到超立方體的一個d-i維自立方體中，而將小於主元的部分送到另一個d-i位的子立方體中，這樣就模擬了快速排序中的劃分算法。子立方體可以這樣選擇：在第i次劃分中判斷第i位是0還是1。劃分算法到處理完所有1維子立方體後結束。接下來對每個頂點中的元素調用串行算法進行局部排序，最後對整個立方體進行一次遍歷便可得到排好序的元素。

比較器絡上的並行排序網[編輯]

比較器網絡（英語：sorting network）一般是指由Batcher比較器構成的網絡。這些比較器均可以執行兩個數之間的比較與條件交換(CCI)操作。Batcher歸併網絡可以由較小的Batcher歸併網絡遞歸地組成。Batcher排序網絡可以分為奇偶排序網絡(Odd-Even Sorting Network)和雙調排序網絡（英語：Bitonic Sorting Net）兩大類。

參閱[編輯]