##### Abstract

Let P be a predicate applicable to permutations. A permutation that satisfies P
is called a generator. Given a permutation $pi$, MinSort_P is the problem of
finding a shortest sequence of generators that, when composed with $pi$, yields
the identity permutation. The length of this sequence is called the P distance of
$pi$. Diam_P is the problem of finding the longest such distance for
permutations of a given length. MinSort_P and Diam_P, for some choices of
P, have applications in the study of genome rearrangements and in the design of
interconnection networks.
This dissertation considers generators that are swaps, reversals, or block-moves.
Distance bounds on these generators are introduced and the corresponding
problems are investigated. Reduction results, graph-theoretic models, exact and
approximation algorithms, and heuristics for these problems are presented.
Experimental results on the heuristics are also provided.
When the bound is a function of the length of the permutation, there are several
sorting problems such as sorting by block-moves and sorting by reversals whose
bounded variants are at least as difficult as the corresponding unbounded
problems. For some bounded problems, a strong relationship exists between
finding optimal sorting sequences and correcting the relative order of individual
pairs of elements. This fact is used in investigating MinSort_P and Diam_P for
two particular predicates.
A short block-move is a generator that moves an element at most two positions
away from its original position. Sorting by short block-moves is solvable in
polynomial time for two large classes of permutations: woven bitonic
permutations and woven double-strip permutations. For general permutations, a
polynomial-time (4/3)-approximation algorithm that computes short block-move
distance is devised. The short block-move diameter for length-n permutations is
determined.
A short swap is a generator that swaps two elements that have at most one
element between them. A polynomial-time 2-approximation algorithm for
computing short swap distance is devised and a class of permutations where the
algorithm computes the exact short swap distance is determined. Bounds for the
short swap diameter for length-n permutations are determined.