DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

Partial Quicksort and Quickpartitionsort

Conrado Martínez, Uwe Rösler

Abstract


Partial Quicksort sorts the l smallest elements in a list of length n. We provide a complete running time analysis for this combination of Find and Quicksort. Further we give some optimal adapted versions, called Partition Quicksort, with an asymptotic running time c1llnl+c2l+n+o(n). The constant c1 can be as small as the information theoretic lower bound log2 e.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional