PSRS算法適合處理大批量的數據。
基本介紹
- 中文名：PSRS算法
- 學科：計算機
問題的初步處理,算法描述,算法分析,
問題的初步處理
PSRS算法（Parallel Sorting by Regular Sampling）：首先設待處理里序列長n，並行機上有p個處理器。為了使問題簡單，我們假設n是p的整倍數。於是將這n個元素劃分為p段，每段中有n/p個元素，將這p段分給p個處理器。注意，執行PSRS算法的並行機必須是多指令流多數據流（MIMD）的。
算法描述
- 讓各個處理器並行的調用串列排序算法進行局部排序；
- 從每個有序段中選p個樣本元素，共個樣本元素（採樣）；、
- 對樣本元素排序；
- 從樣本元素中選p-1作為劃分元素，並播送給其餘的處理器；
- 各個處理器根據劃分元素對局部序列進行劃分（分為p段）；
- 各個處理器將每一段按段號交換到相應序列號的處理器；
- 在各個處理器中使用串列算法再次進行局部排序。
算法分析
如果注意到一個好的串列排序算法的時間複雜度為
那么，容易證得上述PSRS算法的時間複雜度在時
為
。
缺點我們注意到，在第五步進行主元劃分時時可能會引起不均勻性，即位於某兩個主元之間的元素可能要多一些（多於
個）。我們可以證明，在算法中進行到第六步全局交換時，可能會有某一個處理器中數據達到
個；這樣引起的直接後果是處理器負載不均勻，那么在歸併排序中可能會引起排序時間的不均勻。
