Improved Upper Bound for Sorting by Short Swaps

Hong Kong, SAR, China May 10-May 12

DOI Bookmark:

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

2004 International Symposium on Paral ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	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

	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

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.