Asymptotic distribution theory for Hoare's selection algorithm

verfasst von

Rudolf Grübel, Uwe Rösler

Abstract

We investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds the lth smallest in a set of n numbers. Letting n tend to infinity and considering the values l = 1,⋯,n simultaneously we obtain a limiting stochastic process. This process admits various interpretations: it arises in connection with a representation of real numbers induced by nested random partitions and also in connection with expected path lengths of a random walk in a random environment on a binary tree.

Organisationseinheit(en)

Institut für Versicherungs- und Finanzmathematik

Externe Organisation(en)

Christian-Albrechts-Universität zu Kiel (CAU)

Typ

Artikel

Journal

Advances in applied probability

Band

28

Seiten

252-269

Anzahl der Seiten

18

ISSN

0001-8678

Publikationsdatum

03.1996

Publikationsstatus

Veröffentlicht

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Statistik und Wahrscheinlichkeit, Angewandte Mathematik

Elektronische Version(en)

https://doi.org/10.1017/S000186780002735X (Zugang: Geschlossen)