Sorting Network (1) - 一汁三菜

「アルゴリズムイントロダクション第3巻精選トピックス」の第28章のテーマ「ソーティングネットワーク」。今年度の某大学院修士課程の筆記試験の1問目が、これについての問題でした。
$(x',y')=(\min(x,y),\max(x,y))$ 　で定義される比較器を考えます。一般的には、次のような回路の形で表されます。

つまり、2つの入力のうち小さい方を上から出力し、大きい方を下から出力するような回路です。
比較器を複数組み合わせて使う時に、こんな図をいちいち描くのは面倒です。なので、次のように略記します。

この比較器は、常にある決まった定数時間で結果を返す物とします。つまり、実行時間がO(1)です。
比較器を複数組み合わせて作ったn入力n出力の回路を「比較ネットワーク」と言います。但し比較ネットワークには、フィードバック*1があってはいけません。

上の回路が比較ネットワークです。この図を見ると、一番左側にある2つの比較器は、どちらが先に実行されても、あるいは同時に実行されても回路全体の出力に影響が無い事が分かります。こういう時は、それぞれの比較器は同じ時刻に入力を受け取って、同じ時刻に出力を返す事が出来ます。つまり、並列に実行が出来るのです。その次以降にある2つの比較器も、初段の比較器から出力が得られ次第、並列に実行する事が出来ます。結果的に、この回路は比較器を4つ組み合わせて構成した回路であるにも関わらず、2つ分の比較器の実行時間のみで回路全体の出力を得る事が出来るのです。
比較ネットワークが、常に入力を昇順ソートして出力するような回路である時、これを「ソーティングネットワーク」と言います。

ソーティングネットワークの定義まで(自分が)理解したので、今回はここまで。次回は、実行時間を最小にするようなソーティングネットワークについての記事になる予定です。

*1:ある回路の出力を、その回路より前段にある回路の入力に接続する事。