{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T10:53:08Z","timestamp":1656931988277},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T00:00:00Z","timestamp":1534204800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>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.<\/jats:p><jats:p>An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proved.<\/jats:p>","DOI":"10.1017\/s096354831800041x","type":"journal-article","created":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T08:14:50Z","timestamp":1534234490000},"page":"485-518","source":"Crossref","is-referenced-by-count":1,"title":["Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths"],"prefix":"10.1017","volume":"28","author":[{"given":"MARTIN","family":"AUM\u00dcLLER","sequence":"first","affiliation":[]},{"given":"MARTIN","family":"DIETZFELBINGER","sequence":"additional","affiliation":[]},{"given":"CLEMENS","family":"HEUBERGER","sequence":"additional","affiliation":[]},{"given":"DANIEL","family":"KRENN","sequence":"additional","affiliation":[]},{"given":"HELMUT","family":"PRODINGER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"S096354831800041X_ref3","unstructured":"Aum\u00fcller M. , Dietzfelbinger M. , Heuberger C. , Krenn D. and Prodinger H. (2016) Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort. In Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms."},{"key":"S096354831800041X_ref9","unstructured":"Hennequin P. (1991) Analyse en moyenne d'algorithmes : Tri rapide et arbres de recherche. PhD thesis, \u00c9cole Polytechnique, Palaiseau."},{"key":"S096354831800041X_ref16","unstructured":"OEIS (2017) The On-Line Encyclopedia of Integer Sequences. oeis.org"},{"key":"S096354831800041X_ref15","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1007\/s00453-015-0041-7","article-title":"Analysis of pivot sampling in dual-pivot quicksort: A holistic analysis of Yaroslavskiy's partitioning scheme.","volume":"75","author":"Nebel","year":"2016","journal-title":"Algorithmica"},{"key":"S096354831800041X_ref19","volume-title":"EvaluateMultiSums V0.96","author":"Schneider","year":"2015"},{"key":"S096354831800041X_ref24","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/2629340","article-title":"Average case and distributional analysis of dual-pivot quicksort","volume":"11","author":"Wild","year":"2015","journal-title":"ACM Trans. Algorithms"},{"key":"S096354831800041X_ref11","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"Knuth","year":"1998"},{"key":"S096354831800041X_ref6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"Flajolet","year":"2009"},{"key":"S096354831800041X_ref17","unstructured":"SageMath (2016) SageMath Mathematics Software (Version 7.4). www.sagemath.org"},{"key":"S096354831800041X_ref1","unstructured":"Ablinger J. (2015) HarmonicSums V1.0, RISC. www.risc.jku.at\/research\/combinat\/software\/HarmonicSums\/"},{"key":"S096354831800041X_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/2743020"},{"key":"S096354831800041X_ref4","unstructured":"Aum\u00fcller M. , Dietzfelbinger M. , Heuberger C. , Krenn D. and Prodinger H. (2016) Dual-pivot quicksort: Optimality, analysis and zeros of associated lattice paths. arxiv.org\/abs\/1611.00258"},{"key":"S096354831800041X_ref7","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"Graham","year":"1994"},{"key":"S096354831800041X_ref21","unstructured":"Sedgewick R. (1975) Quicksort. PhD thesis, Stanford University."},{"key":"S096354831800041X_ref8","unstructured":"Hackl B. and Krenn D. (2015) Asymptotic expansions in SageMath (module in SageMath 6.10 beta2). trac.sagemath.org\/17601"},{"key":"S096354831800041X_ref10","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","article-title":"Quicksort.","volume":"5","author":"Hoare","year":"1962","journal-title":"Comput. J."},{"key":"S096354831800041X_ref12","doi-asserted-by":"publisher","DOI":"10.1201\/b18255-13"},{"key":"S096354831800041X_ref18","first-page":"1","article-title":"Symbolic summation assists combinatorics.","volume":"56","author":"Schneider","year":"2007","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"S096354831800041X_ref13","doi-asserted-by":"publisher","DOI":"10.1201\/9781420059847"},{"key":"S096354831800041X_ref14","volume-title":"Lattice Path Counting and Applications","author":"Mohanty","year":"1979"},{"key":"S096354831800041X_ref20","unstructured":"Schneider C. (2015) Sigma V1.81, RISC. www.risc.jku.at\/research\/combinat\/software\/Sigma\/"},{"key":"S096354831800041X_ref22","unstructured":"Wild S. (2013) Java 7's dual pivot quicksort. Master's thesis, Universit\u00e4t Kaiserslautern. https:\/\/kluedo.ub.uni-kl.de\/files\/3463\/wild-master-thesis.pdf"},{"key":"S096354831800041X_ref23","unstructured":"Wild S. (2016) Dual-pivot quicksort and beyond: Analysis of multiway partitioning and its practical potential. PhD thesis, Universit\u00e4t Kaiserslautern."},{"key":"S096354831800041X_ref25","unstructured":"Yaroslavskiy V. (2009) Replacement of quicksort in java.util.arrays with new dual-pivot quicksort (archived version of the discussion in the OpenJDK mailing list). mail.openjdk.java.net\/pipermail\/core-libs-dev\/2009-September\/002630.html"},{"key":"S096354831800041X_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2963102"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831800041X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T09:19:30Z","timestamp":1564046370000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831800041X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,14]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["S096354831800041X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831800041x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,14]]}}}