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$.
Discrete Mathematics & Theoretical Computer Science
