Computing Time for Sorting Roughly Sorted Sequences

Yoshihide IGARASHI  

IEICE TRANSACTIONS (1976-1990)   Vol.E72   No.3   pp.229-234
Publication Date: 1989/03/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity

Full Text: PDF>>
Buy this Article

A sequence α(a1,,an) is k-sorted if and only if α satisfies the condition: for all i, j in {1,,n}, ijk implies aiaj. A local characterization of k-sorted sequences is given. An algorithm for sorting k-sorted sequences is designed, and its time efficiency is analysed. For each k1, a lower bound on the number of comparisons needed to sort k-sorted sequences is obtained by an estimate of the number of k-sorted sequences of length n and a decision tree argument. We show that 0.6947 n and 1.1265 n are average case lower bounds on the numbers of comparisons for sorting 1-sorted and 2-sorted sequences of length n, respectively.