キューブソート

キューブソート

クラス	ソートアルゴリズム
データ構造	配列
最悪のパフォーマンス	O ( n log n )
最悪の場合の空間複雑度	Θ( n )
最適	?

キューブソートは、ソート対象となるキーから自己均衡型多次元配列を構築する並列ソートアルゴリズムです。軸の長さがほぼ等しいため、構造は立方体に似ています。各キーを挿入すると、立方体は迅速に配列に変換されます。 ^{[ 1 ]}

C言語で書かれたキューブソートの実装は2014年に公開されました。^{[ 2 ]}

手術

キューブソートのアルゴリズムは、各軸上で特殊な二分探索を用いて要素を挿入する位置を見つけます。軸が大きくなりすぎると、軸は分割されます。小さな配列では、挿入ごとに4回の二分探索のみを実行するため、参照の局所性は最適です。多数の小さな動的配列を使用することで、単一の大きな配列への挿入にかかる高コストを回避できます。

参考文献

1. Cypher, Robert; Sanz, Jorge LC (1992). 「Cubesort: S-sortersを用いたN個のデータ項目のソートのための並列アルゴリズム」. Journal of Algorithms . 13 (2): 211– 234. doi : 10.1016/0196-6774(92)90016-6 .
2. イーゴリ・ファン・デン・ホーフェン (2014 年 6 月 22 日)。「キューブソート」。コードプロジェクト.com。

外部リンク

• 「C言語によるキューブソートの記述と実装」 。2020年10月8日時点のオリジナルよりアーカイブ。
• ロルフ・ニーダーマイヤー(1996)。 「再帰的に分割できる問題」。アルゴリズムと計算。コンピューターサイエンスの講義ノート。 Vol. 1178. シュプリンガー ベルリン ハイデルベルク。ページ 187–188。土井: 10.1007/BFb0009494。eISSN  1611-3349。ISBN 978-3-540-62048-8. ISSN  0302-9743 .（一言）