Computing and ranking measures of presortedness

Abstract

To take advantage of existing order in a sequence when sorting, we consider the problem of evaluating the value of a metric function that estimates the quantity of the order information. A number of algorithms for computing such measures of presortedness are presented. While showing that some measures are linear computable, we demonstrate that for any measure M and for any presortedness sequence X, the value of M(X) can be computed (or approximated) efficiently using a M-adaptive sorting algorithm. The lower bounds on computing measures of presortedness are also given. The method for comparing different presortedness measures, which helps to understand the relationship between different measures and to examine the degree of the sortedness in a sequence with respect to measures, is discussed. We proposed some results that are useful for relating combinatorial properties of the measures to their algorithmic properties.

Keywords:

• Sorting
• presortedness
• algorithms
• measures
• permutations
• partial orders