Faster Algorithms for Sorting by Transpositions and Sorting by Block-Interchanges

摘要

In this paper, we present a new data structure-permutation tree to improve the running time of sorting permutation by transpositions and sorting permutation by block-interchanges. The 1.5-approximation algorithm for sorting permutation by transpositions has time complexity O(n~(3/2) (log n)~(1/2)). By the permutation tree, we can improve this algorithm to achieve time complexity O(n log n). We can also improve the algorithm for sorting permutation by block interchanges to make its time complexity from O(n~2) down to O(n log n).