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 <>
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

  • HAL Id : hal-01185579, version 1

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. ⟨hal-01185579⟩

Share

Metrics

Record views

191

Files downloads

1211