Roughly Sorting: A Generalization of Sorting

概要

論文の詳細を見る
A Sequenceα=(a_l, . . . ,a_n) is k-sorted if and only if for all 1 <le; i,j <le; n, i<j-k implies a_i ≤ a_j. A k-sorting algorithm called k-Bubblesort is first designed, since it is a generalization of Bubblesort. Next, a k-sorting algorithm called k-Quicksort is designed, as well as an algorithm for transforming a rougly sorted sequence into a less roughly sorted sequence. It is shown that k-Quicksort is time-optimal within a constant factor if k satisfies a certain condition. Parallel implementation of k-Bubblesort and k-Quicksort are also discussed.
一般社団法人情報処理学会の論文
1991-03-31