Batcher合併網路

Batcher排序網路(英語:Batcher odd–even mergesort)是由一系列Batcher比較器(Batcher's Comparator)組成的。Batcher比較器是指在兩個輸入端給定輸入x,y,再在兩個輸出端輸出最大值max{x,y}和最小值min{x,y}。

比較器網路是用Batcher比較器連成的完成某一功能的網路。

所謂雙調序列(Bitonic Sequence)是指由一個非嚴格增序列X和非嚴格減序列Y(其中X的最小元素正好是Y的最大元素)構成的序列,比如序列(23,10,8,3,5,7,11,78)。

定義:一個序列a1,a2,…,an是雙調序列,如果:

  1. 存在一個ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立;或者
  2. 序列能夠迴圈移位滿足條件(1)

奇偶合併網路

編輯

輸入兩個已排好序的序列,對這兩個序列進行合併排序,在串行演算法中的時間複雜度為O(n)。在平行計算中可以用奇偶合併演算法來實現的。以輸入的兩個4元素有序序列為A和B為例,首先將這兩個序列進行逆洗牌(Unshuffle)得到兩個序列:其中一個是由A,B中奇數號元素組成的序列,記作奇序列OM,另一個則是由A,B中偶數號元素組成的序列,記作偶序列序列EM。接著將OM送入(2,2)奇合併器中,將EM送入(2,2)偶合併器中。於是得到一組有序的奇序列和一組有序偶序列。最後除了奇序列一個元素之外將這兩個序列進行洗牌(Shuffle)比較操作即可得到一個有序序列。

演算法的遞迴性:一個n階的合併器是由兩個n/2階的合併器加一個洗牌比較網路構成的。比如上面的兩個(2,2)合併器和最後的洗牌比較網路就構成了一個(4,4)的合併器。

一個四階奇偶合併的例子:假設合併前的的序列是(1,5,7,6)和(2,3,4,9),那麼第一次操作就將(1,2,7,4)送入(2,2)合併器中合併,得到結果為(1,2,4,7);(5,3,6,9)送入(2,2)合併器中合併,得到結果為(3,5,6,9),接著將這兩個排號序的序列進行洗牌比較:(1,3<->2,5<->4,6<->7,9)=>(1,2,3,4,5,6,7,9)。

可以證明這個演算法是正確的,我們要用到高德納(Donald Ervin Knuth)的0-1原理,我們發現,對於輸入的任意兩個有序的0,1序列,奇序列與偶序列正好相差0個,1個或2個0。由於奇序列的第一個元素不參與最後的洗牌比較,所以參與比較的0,1數偶只有0個或1個,所以對0,1序列一定能夠得到正確的排序。故而對任意的序列,奇偶合併網路可以產生正確的排序。

雙調合併網路

編輯

雙調合併網路是基於Batcher定理而構建的。Batcher定理是說將任意一個長為2n的雙調序列A分為等長的兩半X和Y,將X中的元素與Y中的元素一一按原序比較,即  比較,將較大者放入MAX序列,較小者放入MIN序列。則得到的MAX和MIN序列仍然是雙調序列,並且MAX序列中的任意一個元素不小於MIN序列中的任意一個元素。

根據這個原理,我們可以將一個輸入的n元素雙調序列首先通過洗牌比較操作得到一個MAX序列和一個MIN序列,然後通過兩個n/2階雙調合併器處理就可以得到一個有序序列。

這個演算法也是遞迴的,因為n階的雙調合併器是由一個洗牌比較網路兩個n/2階的雙調合併器組成的。

參閱

編輯