資料結構與演算法
在 GPU 這類平行處理裝置上排序時，有時會使用雙調排序（bitonic sort）這類比較與交換步驟固定的排序（排序網路），其理由為下列何者？
- A比較次數為 O(n)，少於比較排序的下限 O(n log n)
- B它是穩定排序，能保持相同鍵元素的順序
- C要比較與交換哪些元素的組合，與資料的值無關而事先決定，因此大量執行緒能以相同步驟同時處理，分支也一致
查看答案與解析
正確答案：C. 要比較與交換哪些元素的組合，與資料的值無關而事先決定，因此大量執行緒能以相同步驟同時處理，分支也一致
在雙調排序中，各階段要比較的元素組合只由索引決定，同一階段內的比較與交換全部可以同時進行。n = 2ᵏ 個資料以 k(k+1)/2 個階段完成排序，16個需要10個階段、合計80次比較，1,024個需要55個階段、合計28,160次比較。比較總數為 O(n log² n)，比快速排序等多，但因為步驟不隨資料改變，在 GPU 這種大量執行緒執行相同指令的裝置上不會發生分支發散，能有效率地運作。只靠比較來排序的方法，比較次數不可能少於 O(n log n)，雙調排序一般也不是穩定排序。
- A. 比較排序的比較次數不可能少於 O(n log n)，雙調排序的比較總數為 O(n log² n)。
- B. 雙調排序也會交換相距很遠的元素，因此一般不穩定。
- C. 正確。步驟與資料無關，因此大量執行緒能讓分支一致、同時處理。