






















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 $α\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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。