2013/07/31 by Benjamin Dadoun, Dadoun, Benjamin, Ralph Neininger +1
Computer Science · Mathematics · #68P10 #68Q25 #Bayesian Methods and Mixture Models #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #Primary 60F05 #Probability (math.PR) #Stochastic processes and statistical mechanics #secondary 60C05
paper · doi:10.48550/arxiv.1307.8403
openalex publication_date 2013/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.