On sorting by 3-bounded transpositions

Abstract

Abstract Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323–352] 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 show that to sort any permutation via correcting hops and skips,⌊ n/2⌋ correcting skips suffice. We also present a tighter analysis of the 4 3 approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H n of those permutations of S n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G n⊆ S n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.