データ構造とアルゴリズム
GPUのような並列処理の装置で並べ替えを行うときに、バイトニックソートのような、比較・交換の手順が決まったソート(ソーティングネットワーク)が使われることがある。その理由として正しいものはどれか。
- A比較の回数が O(n) で、比較によるソートの下限 O(n log n) より少ないから
- B安定なソートで、同じキーの要素の順番が保たれるから
- Cどの要素の組を比較・交換するかがデータの値によらず前もって決まっているので、多数のスレッドが同じ手順で同時に処理でき、処理の分岐もそろうから
答えと解説を見る
正解：C. どの要素の組を比較・交換するかがデータの値によらず前もって決まっているので、多数のスレッドが同じ手順で同時に処理でき、処理の分岐もそろうから
バイトニックソートでは、各段で比べる要素の組が添字だけで決まり、1つの段の中の比較・交換はすべて同時に行えます。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. 正しい。手順がデータによらないので、多数のスレッドで同時に、分岐をそろえて処理できます。