On Sorting by 3-Bounded Transpositions

Heath and Vergara (2) proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better. We obtain a complete characterization of the set Gn ⊆ Sn of all correcting-hop-free permutations. We describe an efficient algorithm to optimally sort a permutation in Gn using skips and hops. We study the class Hn of those permutations of Sn which can be sorted using correcting hops alone. We exhibit an interesting relation between Gn and Hn. The notion of correcting skips/hops is extended to correcting moves and it is shown that one can efficiently sort a permutation with a minimum number of correcting moves. © 2005 Elsevier Ltd. All rights reserved.