まだまだ続くシェアソート
今回は多次元展開です。
シェアソートは二次元平面上に展開することで高速化を図りましたが、
三次元空間上に展開したらどうなるでしょうか。
まずは、図を見てみましょう。
これが三次元展開の配置です。
三次元方向には段という名前で呼びます。
2段目は1段目の逆、すなわち開始点と終了点が逆になるようにソートを行っていきます。
3段目は1段目と同じようにソートします。
ソート条件は以下のように変化します。
- 段ソートは、常に昇順
- 縦ソートは、奇数段なら昇順、偶数段なら降順
- 横ソートは、段数＋行数が奇数なら昇順、偶数なら降順
この要領で、四次元展開まで行ってみましょう。
四次元方向には棟という名前を付けます。
それぞれの立方体を団地とみなし、1号棟、2号棟と増えていく様子を想像してください。
1号棟は1で始まり、27で終わりました。
2号棟の始まる28は、1号棟の27のあった位置になります。
そして、26の位置が29になり、25の位置が29になり…1の位置が54となります。
つまり、2号棟は3段目に小さい数字が来て、1段目が大きな数字が来ます。
3号棟は1号棟と同じ形で並んでいます。
では、ソート条件を四次元で考えましょう。
- 棟ソートは、常に昇順
- 段ソートは、奇数棟なら昇順、偶数棟なら降順
- 縦ソートは、棟数＋段段が奇数なら昇順、偶数なら降順
- 横ソートは、棟数＋段数＋行数が奇数なら昇順、偶数なら降順
なお、シェアソートが終わった後、逆になっているものを元に戻すことを考えたとき、
棟の逆転→段の逆転→行の逆転と3ステップ踏まないと完全に戻りません。
多次元におけるシェアソートを考えてみましたが、さほど効率が良いように思えません。
次回、多次元シェアソートをもう少し考えて、長々と続いたシェアソートの補足を終わりたいと思います。