10 citations · 74 across the 27 of their papers we have counts for
3 papers · 2 filters
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number…
An Extended Note on the Comparison-optimal Dual Pivot Quickselect
Daniel Krenn
In this note the precise minimum number of key comparisons any dual-pivot quickselect algorithm (without sampling) needs on average is determined. The result is in the form of exac…
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
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 a…