Portal de Periódicos da CAPES

Partial Quicksort and Quickpartitionsort

2010; French association; Volume: DMTCS Proceedings vol. AM,...; Issue: Proceedings Linguagem: Inglês

10.46298/dmtcs.2781

1462-7264

Conrado Martı́nez, Uwe Rösler,

Computational Geometry and Mesh Generation

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