いろいろな変種Quicksortアルゴリズムの比較について
スポンサーリンク
概要
- 論文の詳細を見る
Quicksortについては既にいろいろな研究がなされているが,どのような特徴をもったサンプルデータに対してどのようなアルゴリズムが有効かは必ずしも明確になっていないそこで,種々の特徴をもつサンプルデータに対していろいろなQuicksortの変種アルゴリズムの有効性について実験的に検討した。また,そのアルゴリズムにカットオフを導入した場合には効率がどのように変わるかについても検討した.アルゴリズムの効率を比較するための尺度として,データ中の要素の比較回数および交換回数と,1つのデータに対しての分割アルゴリズム適用回数(再帰呼び出し回数)の3つを用いた.個々の特徴をもつある種類のデータに対するこれら3つの尺度をそれぞれ100回ずつ測定した.測定の結果,今回扱ったデータ全体を通して効率が良かったアルゴリズムは,カットオフを用いた擬中央値ソート,カットオフを用いたDsortである.またすべてソート済み,あるいはすべて逆順のデータでは,カットオフを用いないBsort,Xsort,Ysortが良いアルゴリズムである.あるデータが与えられた場合,そのデータはそのような特徴をもっているかがあらかじめ分かっている場合には,この実験結果が利用できる.
- 一般社団法人情報処理学会の論文
- 1988-11-15
著者
関連論文
- ソフトウェア科学会第4回大会
- 自動改札機収集データによる旅客行動パターンの解明
- GUIを用いたL-systemエディタの開発
- GUIを用いたL-systemエディタの開発
- 翻訳検証テストのためのストリングリソースID(機械翻訳)
- いろいろな変種Quicksortアルゴリズムの比較について
- 構造的な抽象化機能を持つオブジェクト指向言語 : Ondineの概要
- ディジタル・ドキュメント作成支援環境の提案 : Collaborative Framing for Digital Journalism
- 情報処理専門教育について コンピュータリテラシー教育の一事例
- 実時間システム仕様記述法について
- パズルなどの組合せ問題を解く効率のよいプログラムを書くには
- Pascalプログラムに対する呼出数最小のモジュール宣言方法について
- 実時間並行プロセス仕様記述の一考察
- 特性多項式によるプログラム複雑度の特徴づけ
- 形式文法によるプログラム複雑度の特徴づけ
- ソフトウェア生産過程の評価実験に関する考察
- ARMの報告 (実験整数論)
- プログラミング言語とソフトウェア工学
- 長時間連続移動環境下でのバリアフリー施策の社会経済性評価と評価性能向上に資する新しいコミュニケイション手法の研究
- 全国規模の社会調査に基づく各種障碍者の長時間移動特性の研究
- 大都市圏在住の障碍者全般を対象にした長時間移動特性の研究
- 都市政府水準での対知的障碍者社会調査の展開状況と今後の方向性にかんする研究
- 東京圏在住下肢障碍者の地域内移動特性の研究
- HyperCampus: 物理的環境と連動した情報システムの個人化とその応用
- インホォスケープの世界-"知の風景"をめぐって-
- 三次元動画をもちいた電子新聞 (情報メディアの構造とサーチ)
- 20. 再帰呼出しの索表計算法 (アルゴリズムの最近の動向)
- 構造化プログラムにおける非決定性構文と新しいループ構造
- データベースを利用した列車情報案内システムの作成
- 自律分散型鉄道制御シミュレータの設計
- 四次元空間の可視化を支援するシステム : Julia-Mandelbrot空間の可視化
- パズルゲイム
- C++による仕様記述について
- オブジェクト指向言語Smalltalkによる仕様記述
- 京都賞受賞で来日されたD. E. Knuth先生について
- 輪送情報(乗車人員)の視覚化について
- マルチメディアを応用した経営情報システムのユーザ・インターフェースの改善について
- D.E.クヌース先生のコンピュータライフ
- 階層状体系をもつプログラミング言語の考察
- 組合せ論の証明とプログラミング : パリティ検査の一般化 (組合せ構造とグラフ理論)
- 都市間交通における交通機関選択要因の研究
- 日本の叙情歌
- 慶應義塾大学湘南藤沢キャンパスの授業評価
- リアルタイム制御の記述