Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T07:24:18.682Z Has data issue: false hasContentIssue false

Asymptotic distribution theory for Hoare's selection algorithm

Published online by Cambridge University Press:  01 July 2016

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.

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.

Type
General Applied Probability
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, 11961217.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, 17.CrossRefGoogle Scholar
Hoare, C. A. R. (1961) Algorithm 63, Partition; Algorithm 64, Quicksort; Algorithm 65, Find. Commun. ACM 4, 321322.Google Scholar
Hoare, C. A. R. (1962) Quicksort. Comput. J. 5, 1015.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, 770799.Google Scholar
Rösler, U. (1991) A limit theorem for ‘Quicksort’. Theor. Inf. Appl. 25, 85100.Google Scholar
Rösler, U. (1992) A fixed point theorem for distributions. Stoch. Proc. Appl. 42, 195214.Google Scholar
Sedgewick, R. (1990) Algorithms in C. Addison-Wesley, New York.Google Scholar