著者

伍偉鴻 二村 良彦

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2000, no.5(1999-AL-071), pp.73-79, 2000-01-17

---

現在,実際的に最速と考えられている整列法はBentleyのQuicksort(BQ法)である.本稿では,整列済みに近いデータに対してはBQ法の約2倍高速であり,かつ一様乱数列に対してもBQ法よりも高速な整列法LOAS (Leaves Optimal Adaptive Sort)の2つの実現法について報告する.一つは高速であるがスペースをO(N)要し、もう一方は性能は多少落ちるが、スペースをO(√<N>)要するものである。LOASは,数列の葉(数列において自分より小さい隣接要素を持たない要素)の数について最適な整列法である.即ち,数列の長さと葉数を各々Nおよびmとすると,LOASはO(N log m)時間で整列を完了する.実用に供されている4つの整列法(BQ法,GNU Quicksort,GNU Merge sort,多重分割ソートMPS)を含むいくつかの整列法と比較することにより,LOASの高速性を示す.