Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T10:33:58.239Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic distribution theory for Hoare's selection algorithm

Part of: Theory of data Special processes Limit theorems

Published online by Cambridge University Press:  01 July 2016

Rudolf Grübel  and
Uwe Rösler
Rudolf Grübel*
Affiliation:
Universität Hannover and Christian-Albrecht-Universität Kiel
Uwe Rösler*
Affiliation:
Universität Hannover and Christian-Albrecht-Universität Kiel
*
* Postal address: Institut für Mathematische Stochastik, Universität Hannover, Postfach 60 09, D-30060 Hannover, Germany, and Mathematisches Seminar der Universität Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany.
* Postal address: Institut für Mathematische Stochastik, Universität Hannover, Postfach 60 09, D-30060 Hannover, Germany, and Mathematisches Seminar der Universität Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany.
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

STOCHASTIC ALGORITHMSASYMPTOTIC DISTRIBUTIONORDER STATISTICSRANDOM BINARY NUMBERSRANDOM WALK IN A RANDOM ENVIRONMENT

MSC classification

Primary: 60F17: Functional limit theorems; invariance principles 68P10: Searching and sorting
Secondary: 60K99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 28 , Issue 1 , March 1996 , pp. 252 - 269
Copyright
Copyright © Applied Probability Trust 1996 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Athreya, K. B. and Ney, P. E. (1972) Branching Processes. Springer, Berlin.Google Scholar
Bickel, P. and Freedman, D. A. (1981) Some asymptotic theory for the bootstrap. Ann. Statist. 9, 1196–1217.Google Scholar
Billingsley, P. (1968) Convergence of Probability Measures. Wiley, New York.Google Scholar
Devroye, L. (1984) Exponential bounds for the running time of a selection algorithm. J. Comput. Syst. Sci. 29, 1–7.CrossRefGoogle Scholar
Hoare, C. A. R. (1961) Algorithm 63, Partition; Algorithm 64, Quicksort; Algorithm 65, Find. Commun. ACM 4, 321–322.Google Scholar
Hoare, C. A. R. (1962) Quicksort. Comput. J. 5, 10–15.CrossRefGoogle Scholar
Johnson, N. L. and Kotz, S. (1970) Continuous Univariate Distributions–1. Houghton Mifflin, Boston.Google Scholar
Knuth, D. E. (1973) The Art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, Reading.Google Scholar
Rachev, S. T. and Rüschendorf, L. (1995) Probability metrics and recursive algorithms. Adv. Appl. Prob. 27, 770–799.Google Scholar
Rösler, U. (1991) A limit theorem for ‘Quicksort’. Theor. Inf. Appl. 25, 85–100.Google Scholar
Rösler, U. (1992) A fixed point theorem for distributions. Stoch. Proc. Appl. 42, 195–214.Google Scholar
Sedgewick, R. (1990) Algorithms in C. Addison-Wesley, New York.Google Scholar