著者

野崎 昭弘 杉本 俊彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.21, no.2, pp.164-166, 1980-03-15

---

「内部ソートのおそらく最も有用な汎用技法」(クヌース)といわれるクイックソートの長所は平均所要時間が短いことであり 短所は最悪の場合の所要時間がひじょうに長い(項目数nに対してΟ(n^2))ことである.本論文ではクイックソートを改良して 最悪の場合の所要時間を項目数nに対してΟ(n log n)におさえ しかも平均所要時間をほとんど損なわないようにできることを示した.