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

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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.

Originalsprog	Engelsk
Tidsskrift	Combinatorics, Probability & Computing
Antal sider	34
ISSN	0963-5483
DOI	https://doi.org/10.1017/S096354831800041X
Status	Udgivet - 14 aug. 2018

Adgang til dokumentet

10.1017/S096354831800041X

1611.00258Accepteret manuskript, 733 KB

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

Citationsformater

@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",

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

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

Adgang til dokumentet

Fingeraftryk

Citationsformater