A statistical view on exchanges in Quickselect

DOI10.1137/1.9781611973204.4MaRDI QIDQ5194755zbMATH OpenOpenAlexFDO

Authors Benjamin Dadoun, Ralph Neininger

Publication date 17 September 2019

Published in 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Searching and sorting (68P10) Combinatorial probability (60C05)

Abstract: In this paper we study the number of key exchanges required by Hoare's FIND algorithm (also called Quickselect) when operating on a uniformly distributed random permutation and selecting an independent uniformly distributed rank. After normalization we give a limit theorem where the limit law is a perpetuity characterized by a recursive distributional equation. To make the limit theorem usable for statistical methods and statistical experiments we provide an explicit rate of convergence in the Kolmogorov--Smirnov metric, a numerical table of the limit law's distribution function and an algorithm for exact simulation from the limit distribution. We also investigate the limit law's density. This case study provides a program applicable to other cost measures, alternative models for the rank selected and more balanced choices of the pivot element such as median-of-$2t+1$ versions of Quickselect as well as further variations of the algorithm.

Recommendations

• Quickselect and the Dickman Function
• Analysis of quickselect : an algorithm for order statistics
• Distributional analysis of swaps in quick select
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
• Probabilistic analysis of multiple quick select

Cited in

(7)

• Analysis of quickselect : an algorithm for order statistics
• Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm
• Distributional analysis of swaps in quick select
• Probabilistic analysis of multiple quick select
• Analysis of swaps in radix selection
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
• Quickselect and the Dickman Function

This page was built for publication: A statistical view on exchanges in Quickselect

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