Skip to Main content Skip to Navigation
Conference papers

Partial Quicksort and Quickpartitionsort

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 $c_1l\ln l+c_2l+n+o(n)$. The constant $c_1$ can be as small as the information theoretic lower bound $\log_2 e$.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185579
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:32:53 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:49:05 AM

File

dmAM0135.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Conrado Martínez, Uwe Rösler. Partial Quicksort and Quickpartitionsort. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.505-512, ⟨10.46298/dmtcs.2781⟩. ⟨hal-01185579⟩

Share

Metrics

Record views

153

Files downloads

1041