Partial Quicksort and Quickpartitionsort

Conrado Martínez; Uwe Rösler

doi:10.46298/dmtcs.2781

Conrado Martínez ; Uwe Rösler - Partial Quicksort and Quickpartitionsort

dmtcs:2781 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2781

Partial Quicksort and QuickpartitionsortConference paper

Authors: Conrado Martínez ¹; Uwe Rösler ²

1 Departament Llenguatges i Sistemes Informatics,
2 Mathematisches Seminar [Kiel]

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

https://doi.org/10.46298/dmtcs.2781

Source: HAL:hal-01185579v1

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

Section: Proceedings

Published on: January 1, 2010

Imported on: January 31, 2017

Keywords: searching,sorting,Find,Quicksort,divide and conquer algorithm,random algorithm,running time analysis,asymptotic distribution,optimal adapted algorithms,stochastic fixed point equation,contraction method,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

Conrado Martínez ; Uwe Rösler - Partial Quicksort and Quickpartitionsort

Bibliographic References

2 Documents citing this article

Share and export

Consultation statistics