バイトニックソーティングの改良

改良その1
バイトニック列を基本性質に即っり列を二分(便宜上右と左の系列とする)して先頭から比較して大きいほうの数値を選択する。

バイトニックソーティングで一番重要なデータの比較作業。先頭から比較していき比較をしても右の系列の数値のほうが大きくなった時点で比較を終了する。これで約20%の速度向上が見られた。

改良その2
バイトニック列から昇順モノトニック列を生成する。

この時バイトニック列の最大値を検索する。(この場合左から右へ検索)


次に最大値のところ分割しての二つの系列にする。


系列が上記のように二つできる。その系列のうち最大値より後の系列(系列2)をひっくり返す。


すると昇順モノトニック列が出来る。この二系列をマージソーティングをすると


一つのモノトニック列が完成する。
この方法を使用するとバイトニック列をクイックソートするよりも40%以上の速度向上を達成することが出来た。




前へ戻る