著者

伍偉鴻 二村 良彦

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.5, 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の高速性を示す.Two implementations of LOAS(Leaves Optimal Adaptive Sort) are proposed. One implementation is optimized in running time which needs O(N) extra working space and is faster than the fastest Quicksort known, Bentley's Quicksort, by a factor of 2 in practice, the other needs O(√<N>) extra working space which is more practical but loss in efficiency. LOAS runs in O(N log Leaves) time and is optimal with respect to the presortedness measure Leaves which is the number of elements smaller than their neighbors in a given sequence. Evaluation of LOAS together with four other sorting algorithms (Bently's Quicksort, GNU Quicksort, GNU Merge Sort and Multi Partition Sort MPS) is conducted to show the efficiency of LOAS.