著者

二村 良彦 平井 利冶

雑誌

全国大会講演論文集

巻号頁・発行日

vol.50, pp.317-318, 1995-03-15

---

葉数最適整列法LOAS(Leaves-Optimal Adaptive Sort)は,基本的にはマージに基づいた整列法である.それは与えられた数列をまず葉数個の部分列に分割し,次に分割された部分列を2つづつマージする(ただし数列の葉とは,数列において隣人よりも値の小さい要素である).従ってLOASを実現するに際して,適正なマージ戦略を選択することが重要である.本稿に於いては,我々がLOASを実現する際に検討した下記3種類のマージ戦略とその性能について報告する.(1)単純マージ.(2) 2分マージ(binary merge).(3)基本的には単純マージであるが,マージする2つの数列の特徴に応じて2分法を利用したもの.例えば,一方の数列の長さが1のときのみ,その挿入個所を探索する為に2分法を利用したもの.葉数を制御したランダムな順列を用いて各種方式のキー比較回数および実行時間の比較評価をした.その結果,単純マージを利用した最も素朴な方法を陵駕する方式は,現在までには見つかっていない.LOASとその他の整列法との性能比較については報告した.以下では整列すべき数列は配列z(1),...,z(n)に格納されており,これを昇順に整列する場合について考える.