Sorting by exchanging elements at bounded distance.

摘要

We consider the problem of sorting an arbitrary permutation of length n by exchanging two elements at bounded distance k, this has been called "short swap k". If k = 2, we are allowed to exchange two elements that are either adjacent or at distance 2. We show an upper bound of (3/16) n2+ O(n log n) for sorting on a linear permutation, improving the previous (1/4)n 2 upper bound. We also show that there is a short swap 2 sorting network with (1/4)n2+O(n log n) comparators and depth (3/4)n. We generalized the problem by giving an upper bound of (11/90)n2 + O(n log n) for the case k = 3 and an upper bound of (3/(8k))n 2 + O(n log n) for all k > 3, when k is even. We also show a way to build short swap k sorting network with (1/(2k)) n2 + O(n log n) comparators and depth (3/(2k))n.; For the problem of sorting on cyclic permutations, we prove an upper bound of (1/4)n2 + O(n) for sorting by exchanging adjacent element. We show an upper bound of (5/32) n2 + O(n log n), a lower bound of (1/4)n2 + O(n) and a 2-approximation algorithm for sorting by short swap 2.; Given two binary cyclic strings with equal length n and which have the same number of 1s and 0s, we consider the problem of transforming one into the other in the minimum number of steps by exchanging adjacent elements. We show this problem is polynomial solvable by giving an O(n 2) algorithm.