• DocumentCode
    3012948
  • Title

    Improved upper bound for sorting by short swaps

  • Author

    Feng, X. ; Meng, Z. ; Sudborough, I.H.

  • Author_Institution
    Dept. of Comput. Sci., Texas Univ., Dallas, TX, USA
  • fYear
    2004
  • fDate
    10-12 May 2004
  • Firstpage
    98
  • Lastpage
    103
  • Abstract
    We consider the problem of sorting an arbitrary permutation of length n using substring reversals of length 2 or 3. This has been called "short swaps ". We give an upper bound of (5/24) n2 + O(nlogn), improving the previous ( 1/4 ) n2 upper bound. We also show that there is a short swap sorting network with ( 1/4 ) n2 +O(nlogn) comparators and depth n.
  • Keywords
    computational complexity; sorting; 2-approximation algorithm; arbitrary permutation; polynomial time; recursive algorithm; short swap sorting; sorting network; substring reversals; upper bound; Approximation algorithms; Computational biology; Computer science; Polynomials; Sequences; Sorting; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on
  • ISSN
    1087-4089
  • Print_ISBN
    0-7695-2135-5
  • Type

    conf

  • DOI
    10.1109/ISPAN.2004.1300465
  • Filename
    1300465
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3012948