QuickSelect Process and QuickVal Residual Convergence

Abstract

We define a sequence of tree-indexed processes closely related to the operation of the QuickSelect search algorithm (also known as Find) for all the various values of n (the number of input keys) and m (the rank of the desired order statistic among the keys). As a "master theorem" we establish convergence of these processes in a certain Banach space, from which known distributional convergence results as n tends to infinity about (1) the number of key comparisons required are easily recovered (a) when m/n tends to alpha in [0, 1], and (b) in the worst case over the choice of m. From the master theorem it is also easy, for distributional convergence of (2) the number of symbol comparisons required, both to recover the known result in the case (a) of fixed quantile alpha and to establish our main new result in the case (b) of worst-case Find.

Our techniques allow us to unify the treatment of cases (1) and (2) and indeed to consider many other cost functions as well. Further, all our results provide a stronger mode of convergence (namely, convergence in L^p or almost surely) than convergence in distribution. Extensions to MultipleQuickSelect are discussed briefly.

Under mild assumptions on a general class of cost functions, Fill and Nakama (2013) proved that the scaled cost of QuickVal converges in L^p and almost surely to a limit random variable S. For a general cost function, we consider what we term the QuickVal residual.

The residual is of natural interest (especially in light of the previous analogous work on QuickSort). In the case of QuickMin with key-comparisons cost, we are able to calculate---a la Bindjeme and Fill for QuickSort ---the exact (and asymptotic) L^2-norm of the residual. We take the result as motivation for the scaling factor of root n for the QuickVal residual for general population quantiles and for general cost. We then show in general that the scaled QuickVal residual converges in law to a scale-mixture of centered Gaussians. In the motivating case of QuickMin with key-comparisons cost, we also prove convergence of moments. Following Fuchs for QuickSort, this was part of our original attempt at proving convergence in distribution for the scaled QuickVal residual: using the method of moments. However, this approach encountered two roadblocks: first, because the approach is inherently recursive, we don't know how to extend beyond the motivating case; second, in the case of QuickMin with key-comparisons cost, we can show via Krein's condition that the moments of the limiting distribution do not uniquely define a distribution . In the case of QuickVal with general cost functions, it is still an open question whether the limiting residual distribution is uniquely defined by its moments for any value of alpha.