Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort

MaRDI QIDQ4632472zbMATH OpenFDO

Authors Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger, Daniel Krenn, Helmut Prodinger

Publication date 29 April 2019

Full work available at URL https://arxiv.org/abs/1602.04031

zbMATH Keywords

asymptotic enumerationcombinatorial identitydual-pivot quicksortlattice paths

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Searching and sorting (68P10) Analysis of algorithms (68W40)

Abstract: 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.

Recommendations

• Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths
• Probabilistic analysis of the dual-pivot quicksort ``Count
• DUAL PIVOT QUICKSORT
• Optimal Partitioning for Dual Pivot Quicksort
• Optimal partitioning for dual-pivot quicksort

Cited in

(2)

• Probabilistic analysis of the dual-pivot quicksort ``Count
• Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths

This page was built for publication: Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632472)