著者

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

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(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.