X. Feng, I.H. Sudborough, and E. Lu (USA)
Short Swap, Sorting, Algorithm, Gene Rearrangement
A short swap is an operation that switches two elements that have at most one element in between. In this paper, we consider the problem of sorting an arbitrary permutation by short swaps. We give an algorithm which sorts any permutation of length n within (3/16)n2 +O(n log n) steps, improving the previous (5/24)n2 +O(n log n) upper bound.
Important Links:
Go Back
