Improved Upper Bound for Sorting by Short Swaps

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by X. Feng Articles by Z. Meng Articles by I. H. Sudborough

2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)

Hong Kong, SAR, China

May 10-May 12

ISBN: 0-7695-2135-5

	ASCII Text	x
	X. Feng, Z. Meng, I. H. Sudborough, "Improved Upper Bound for Sorting by Short Swaps," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 98, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004.

	BibTex	x
	@article{ 10.1109/ISPAN.2004.1300465, author = {X. Feng and Z. Meng and I. H. Sudborough}, title = {Improved Upper Bound for Sorting by Short Swaps}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {2004}, issn = {1087-4089}, pages = {98}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.1300465}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Improved Upper Bound for Sorting by Short Swaps SN - 1087-4089 SP EP A1 - X. Feng, A1 - Z. Meng, A1 - I. H. Sudborough, PY - 2004 KW - null VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

X. Feng, University of Texas at Dallas

Z. Meng, University of Texas at Dallas

I. H. Sudborough, University of Texas at Dallas

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.1300465

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) n{2} + O(nlogn), improving the previous (1/4) n{2} upper bound. We also show that there is a short swap sorting network with (1/4)n{2} + O(nlogn) comparators and depth n.

Citation:

X. Feng, Z. Meng, I. H. Sudborough, "Improved Upper Bound for Sorting by Short Swaps," ispan, pp.98, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.