On fine fluctuations of the complexity of the QuickSelect algorithm

Abstract

The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key comparisons required by Quickselect considered as a process of the quantiles $\hat{I}\pm \in [0,1]$ converges within a natural probabilistic model after normalization in distribution within the cà dlà g space $D[0,1]$ endowed with the Skorokhod metric. We show that the residual process in the latter convergence after normalization converges in distribution towards a mixture of Gaussian processes in $D[0,1]$. A similar result holds for the related algorithm QuickVal. Our method is applicable to other cost measures such as the number of swaps (key exchanges) required by Quickselect, or cost measures being based on key comparisons taking additionally into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions. For all the arising mixtures of Gaussian limit processes, we also discuss the Hölder continuity of their paths.

Version 1 is an extended abstract published by the 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA24), Art. No. 9, 15 pp, Leibniz Int. Proc. Inform., 302, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024. From Version 2 on it is the full paper version