English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper we study the number of key exchanges required by Hoare's FINDalgorithm (also called Quickselect) when operating on a uniformly distributedrandom permutation and selecting an independent uniformly distributed rank.After normalization we give a limit theorem where the limit law is a perpetuitycharacterized by a recursive distributional equation. To make the limit theoremusable for statistical methods and statistical experiments we provide anexplicit rate of convergence in the Kolmogorov--Smirnov metric, a numericaltable of the limit law's distribution function and an algorithm for exactsimulation from the limit distribution. We also investigate the limit law'sdensity. This case study provides a program applicable to other cost measures,alternative models for the rank selected and more balanced choices of the pivotelement such as median-of-$2t+1$ versions of Quickselect as well as furthervariations of the algorithm.

A statistical view on exchanges in Quickselect