イントロソート
イントロソート（英: introsort）は、David Musser が1997年に設計したソートアルゴリズムである。最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。クイックソートもヒープソートも比較ソートであり、イントロソートも同様である。
クイックソートでは、ピボット（リストを分割する位置）の選択が重要である。リストの先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。ニクラウス・ヴィルトはこれを避けるため、中央の位置をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n2) となる。先頭、最後尾、中央の値の中央値となる位置をピボットにするアルゴリズムもある。実際のデータのソートはこれでほとんどうまくいくが、これを出し抜くように工夫したリストを作ることができ、性能を大幅に低下させることができる。例えば、そのようなリストを使ったDoS攻撃がありうる。
Musser によれば、クイックソートが最悪値を示すようなリストであっても、イントロソートではその1/1200の時間でソートを完了する。Musser は Robert Sedgewick が考案したキャッシュメモリの効果を考慮したソートアルゴリズムも検討した。それは、細かい部分について挿入ソートを1回最後に行うというものである。彼によると、イントロソートではキャッシュミス率は2倍になるが、両端キューを使った実装では劇的に性能を改善できるため、テンプレートライブラリに保持すべきだとしている（特に、キャッシュの保持されている間にソートを行わないこともあるため）。
同様に、Musser は最悪時間でも線形の選択アルゴリズムも考案した。その時間計算量はアントニー・ホーアのアルゴリズムに匹敵する（ホーアのアルゴリズムは選択アルゴリズムとして最も効率的とされているアルゴリズムで、クイックソートを単純に利用している）。これをイントロ選択 (introselect) アルゴリズムと呼ぶ。
2000年6月、SGI C++ Standard Template Library で、Musser のイントロソートの手法を利用した不安定ソートの実装をした[1]。ヒープソートに切り替える再帰の深さは引数で指定でき、最終段は Sedgewick の挿入ソートを使う方式である。挿入ソートに切り替わる再帰の深さは16だった。
脚注 [編集]
参考文献 [編集]
- Musser, David (1997年). “Introspective Sorting and Selection Algorithms”. Software: Practice and Experience (Wiley) 27 (8): 983–993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
- Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.
外部リンク [編集]
- "A guide to Introsort" by Ralph Unden. Javaによる実装例がある。
