在排序固定長度的小陣列時,那些 big-O 優異的演算法往往討不到便宜,而且還很容易因為多餘的操作而拖慢速度。Sorting Network 就是為了排序固定長度的小陣列而發明的。Sorting Network 是一組事先規劃好的比較、交換操作,只要按照固定步驟操作就能將資料排序。

若一個 Sorting Network 滿足某些條件,就可以將操作步驟平行化或者實作成平行排序硬體,這是這類演算法最大的優勢,不過這不是本文的重點。即使在沒有平行化的情況下,Sorting Network 作為循序執行的排序法效能通常也不錯,至少可以狂電 Bubble、Insertion sort,而且所有的動作都是固定的,可以輕易寫成一連串無迴圈的 if-swap 串,這在「big-O不代表一切」的小資料世界裡具有實作優勢。

, ,

novus 發表在 痞客邦 PIXNET 留言(0) 人氣()