2 0 0 0 OA 安全クイックソート
- 著者
- 野崎 昭弘 杉本 俊彦
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.21, no.2, pp.164-166, 1980-03-15
「内部ソートのおそらく最も有用な汎用技法」(クヌース)といわれるクイックソートの長所は平均所要時間が短いことであり 短所は最悪の場合の所要時間がひじょうに長い(項目数nに対してΟ(n^2))ことである.本論文ではクイックソートを改良して 最悪の場合の所要時間を項目数nに対してΟ(n log n)におさえ しかも平均所要時間をほとんど損なわないようにできることを示した.
言及状況
Twitter (2 users, 2 posts, 1 favorites)
まじかーこれは見落していた。
岩波ソフトウェア科学シリーズよりも早いので、これがイントロソートの初出かもしれない
https://t.co/6IRFpI6RbP
個人的にはすごい衝撃、David Musser が1997年に設計したとされるイントロソートと全く同じアイデアが、安全クイックソートという名前で1980年に既に日本人によって公開されていた！！。FORTRANのソース付き。https://t.co/MbJVzmh2tq