著者

二村 良彦 二村 夏彦 遠藤貢一 平井 利治

出版者

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

雑誌

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

巻号頁・発行日

vol.1995, no.32, pp.5-12, 1995-03-17

被引用文献数

4

---

数列が整列されている度合を表す事前整列性測度Leaves(葉数),および事前整列性のよい数列については高速にソートをする適応整列法LOASとその実現法について報告する.LOASはまず与えられた数列を葉数個の区間にO()時間で分割し,次にそれをO( log葉数)時間でマージする整列法である.本稿ではまず葉数とLOASを定義し,次にLOASがLeavesに関して最適であることの証明を与える.最後にLOASの実現法およびその他の適応ソートや実用的なQUICKソート,MERGEソート等との性能比較結果を示す.We propose a new presortedness measure leaves and a new sorting algorithm LOAS (Leaves Optimal Adaptive Sort) which is optimal with respect to the measure. LOAS divides a given sequence X into Leaves (X) sorted subsequences in O(n) time. Then it merges the sequences in O(n log Leaves(X)) time. Implementation techniques and proof of the Leaves-Optimality of the algorithm are described. In order to prove that LOAS is an efficient sorting algorithm, we have conducted systematic evaluation of several sorting algorithms including Quicksort, merge sort, Skip sort and MEL sort.

著者

二村 良彦 大谷 啓記 青木 健一 二村 夏彦

出版者

一般社団法人日本ソフトウェア科学会

雑誌

コンピュータソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.14, no.6, pp.588-605, 1997-11-17

被引用文献数

1

---

長さnの順列を等確率,即ち1/n!で生成するO(n)アルゴリズムは知られている.しかし,整列アルゴリズム等の精密な評価のためには,このような一様乱順列による評価では不十分である.例えば,一様乱順列に含まれる葉数(自分よりも小さい隣人を持たない要素の個数),ランズ,および上昇部分の個数(即ちn-ランズ)は,平均各々約(n+1)/3,(n+1)/2,および(n-1)/2である.これは一様乱順列が極めて偏った特性を有することを意味する.アルゴリズムの性能に影響を及ぼす性質(例えば葉数)を制御しながらランダムに順列を生成し,それを用いてアルゴリズムの性能を評価する必要がある.本稿では,順列から非負の整数上への関数および関数値を順列の特性指標と呼ぶ.特性指標の中でも,順列の葉数,ランズ,上昇部分数等に対応するクラスを単純指標と呼び,それを形式的に定義する.そして長さn,単純指標mを持つ乱順列をO(nm)で生成する計算機オーバーフロー(またはアンダーフロー)無しの方法を提案する.また,単純指標が葉数である場合には順列をO(n)で生成する実用的近似方式について報告する.