安全クイックソート
スポンサーリンク
概要
- 論文の詳細を見る
「内部ソートのおそらく最も有用な汎用技法」(クヌース)といわれるクイックソートの長所は平均所要時間が短いことであり, 短所は最悪の場合の所要時間がひじょうに長い(項目数nに対してΟ(n^<2)>))ことである. 本論文ではクイックソートを改良して, 最悪の場合の所要時間を項目数nに対してΟ(n log n)におさえ, しかも平均所要時間をほとんど損なわないようにできることを示した.
- 一般社団法人情報処理学会の論文
- 1980-03-15
著者
関連論文
- 多値論理 (<特集>非標準論理とその応用)
- 研究の環境 : 極限状況からのアプローチ(8.環境)(極限へのアプローチ)
- 4. 行列積の漸近的計算量 (アルゴリズムの最近の動向)
- 双端キューの並列結合によるソーティングについて
- 計算の複雑さについて
- 安全クイックソート
- Dequesによる順列のソーティングについて
- 多項式の前処理つき計算の複雑さについて
- 多値論理関数族の完全性--歴史と… (多値論理)
- 離散数学とはなにか (離散数学のすすめ--現代数学の新天地)
- アルゴリズムについて (アルゴリズムの発見)
- アルゴリズムとグラマ (生成発展系--アルゴリズムとグラマ)
- オ-トマトン系の完全性 (オ-トマトン構造)
- 言語と数学 (言語)
- 知識構造と数学 (知識構造)
- 論理素子集合の順序回路に基づく完全性