Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths

Martin Aumüller; Martin Dietzfelbinger; Clemens Heuberger; Daniel Krenn; Helmut Prodinger

doi:10.1017/S096354831800041X

Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths

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

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, 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 proved.

Original language	English
Journal	Combinatorics, Probability & Computing
Number of pages	34
ISSN	0963-5483
DOIs	https://doi.org/10.1017/S096354831800041X
Publication status	Published - 14 Aug 2018

Keywords

combinatorial identity
asymptotic enumeration
lattice paths
Dual-pivot quicksort

Access to Document

10.1017/S096354831800041X

1611.00258Accepted author manuscript, 733 KB

https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/dualpivot-quicksort-optimality-analysis-and-zeros-of-associated-lattice-paths/180377D10918C761E5FA26BE1ACE58BCLicence: Other

Cite this

@article{1136845cea3f40768a999c86af3cc079,

title = "Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths",

abstract = "We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, 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 proved.",

keywords = "combinatorial identity, asymptotic enumeration, lattice paths, Dual-pivot quicksort, combinatorial identity, asymptotic enumeration, lattice paths, Dual-pivot quicksort",

author = "Martin Aum{\"u}ller and Martin Dietzfelbinger and Clemens Heuberger and Daniel Krenn and Helmut Prodinger",

year = "2018",

month = aug,

day = "14",

doi = "10.1017/S096354831800041X",

language = "English",

journal = "Combinatorics, Probability & Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths

AU - Aumüller, Martin

AU - Dietzfelbinger, Martin

AU - Heuberger, Clemens

AU - Krenn, Daniel

AU - Prodinger, Helmut

PY - 2018/8/14

Y1 - 2018/8/14

N2 - We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, 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 proved.

AB - We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, 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 proved.

KW - combinatorial identity

KW - asymptotic enumeration

KW - lattice paths

KW - Dual-pivot quicksort

KW - combinatorial identity

KW - asymptotic enumeration

KW - lattice paths

KW - Dual-pivot quicksort

U2 - 10.1017/S096354831800041X

DO - 10.1017/S096354831800041X

M3 - Journal article

SN - 0963-5483

JO - Combinatorics, Probability & Computing

JF - Combinatorics, Probability & Computing

ER -

Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths

Abstract

Keywords

Access to Document

Fingerprint

Cite this