Probabilistic Analysis of the Dual-Pivot Quicksort “Count”

DOI10.1137/1.9781611975062.1zbMATH Open1430.68075arXiv1710.07505OpenAlexW2765215077MaRDI QIDQ5195099

Ralph Neininger, Jasmin Straub

Publication date: 18 September 2019

Published in: 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Abstract: Recently, Aum"uller and Dietzfelbinger proposed a version of a dual-pivot quicksort, called "Count", which is optimal among dual-pivot versions with respect to the average number of key comparisons required. In this note we provide further probabilistic analysis of "Count". We derive an exact formula for the average number of swaps needed by "Count" as well as an asymptotic formula for the variance of the number of swaps and a limit law. Also for the number of key comparisons the asymptotic variance and a limit law are identified. We also consider both complexity measures jointly and find their asymptotic correlation.

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Related Items (1)

Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm

This page was built for publication: Probabilistic Analysis of the Dual-Pivot Quicksort “Count”

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