Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
- ,
- Martin Dietzfelbinger,
- Clemens Heuberger,
- Daniel Krenn,
- Helmut Prodinger
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-review
Open access
Publication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewOriginal language
EnglishPublication milestones
- Published - 04/07/2016
Publication status
Published - 04/07/2016
Publisher
Jagiellonian University in KrakowHost publication title
Proceedings of the 27th Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of AlgorithmsAbstract
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic
comparison-optimal partitioning strategy, the other with a closely related algorithmic strategy. For both
we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we
provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis
of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
comparison-optimal partitioning strategy, the other with a closely related algorithmic strategy. For both
we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we
provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis
of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
Access to documents
Final published version
Related Event
Title
International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms
Event type
ConferenceDegree of recognition
International eventDate
04/07/2016 - 07/07/2016Location
Jagiellonian UniversityKrakówPoland