Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-15T01:30:33.015Z Has data issue: false hasContentIssue false
  • English
  • Français

Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect

Part of: Limit theorems Algorithms - Computer Science

Published online by Cambridge University Press:  22 February 2016

James Allen Fill  and
Takehiko Nakama
James Allen Fill*
Affiliation:
Johns Hopkins University
Takehiko Nakama*
Affiliation:
Johns Hopkins University
*
∗ Postal address: Department of Applied Mathematics and Statistics, Johns Hopkins University, 3400 N. Charles Street, Baltimore, MD 21218-2682, USA. Email address: [email protected]
∗∗ Current address: European Centre for Soft Computing, Edificio de Investigación, Calle Gonzalo Gutiérrez Quirós S/N, 33600 Mieres, Asturias, Spain.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

When the search algorithm QuickSelect compares keys during its execution in order to find a key of target rank, it must operate on the keys' representations or internal structures, which were ignored by the previous studies that quantified the execution cost for the algorithm in terms of the number of required key comparisons. In this paper we analyze running costs for the algorithm that take into account not only the number of key comparisons, but also the cost of each key comparison. We suppose that keys are represented as sequences of symbols generated by various probabilistic sources and that QuickSelect operates on individual symbols in order to find the target key. We identify limiting distributions for the costs, and derive integral and series expressions for the expectations of the limiting distributions. These expressions are used to recapture previously obtained results on the number of key comparisons required by the algorithm.

Keywords

QuickSelectQuickQuantQuickVallimit distributionalmost-sure convergenceLp-convergencesymbol comparisonprobabilistic source

MSC classification

Primary: 60F25: $L^p$-limit theorems
Secondary: 68W40: Analysis of algorithms
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 45 , Issue 2 , June 2013 , pp. 425 - 450
Copyright
© Applied Probability Trust 

References

Billingsley, P. (1995). Probability and Measure, 3rd edn. John Wiley, New York.Google Scholar
Chung, K. L. (2001). A Course in Probability Theory, 3rd edn. Academic Press, San Diego, CA.Google Scholar
Clément, J., Flajolet, P. and Vallée, B. (2001). Dynamical sources in information theory: a general analysis of trie structures. Algorithmica 29, 307–369.Google Scholar
Devroye, L. (1984). Exponential bounds for the running time of a selection algorithm. J. Comput. System Sci. 29, 1–7.Google Scholar
Devroye, L. (2001). On the probablistic worst-case time of “Find”. Algorithmica 31, 291–303.CrossRefGoogle Scholar
Fill, J. A. (2013). Distributional convergence for the number of symbol comparisons used by QuickSort. Ann. Appl. Prob. 23, 1129–1147.Google Scholar
Fill, J. A. and Janson, S. (2012). The number of bit comparisons used by Quicksort: an average-case analysis. Electron. J. Prob. 17, 22pp.Google Scholar
Fill, J. A. and Nakama, T. (2010). Analysis of the expected number of bit comparisons required by Quickselect. Algorithmica 58, 730–769.CrossRefGoogle Scholar
Grübel, R. (1998). Hoare's selection algorithm: a Markov chain approach. J. Appl. Prob. 35, 36–45.Google Scholar
Grübel, R. and Rösler, U. (1996). Asymptotic distribution theory for Hoare's selection algorithm. Adv. Appl. Prob. 28, 252–269.Google Scholar
Hoare, C. A. R. (1961). Find (algorithm 65). Commun. ACM 4, 321–322.Google Scholar
Hwang, H.-K. and Tsai, T.-H. (2002). Quickselect and the Dickman function. Combinatorics Prob. Comput. 11, 353–371.CrossRefGoogle Scholar
Knuth, D. E. (1972). Mathematical analysis of algorithms. In Information Processing 71 (Proc. IFIP Congress, Ljubljana, 1971), Vol. 1, North-Holland, Amsterdam, pp. 19–27.Google Scholar
Lent, J. and Mahmoud, H. M. (1996). Average-case analysis of multiple Quickselect: an algorithm for finding order statistics. Statist. Prob. Lett. 28, 299–310.CrossRefGoogle Scholar
Mahmoud, H. M. and Smythe, R. T. (1998). Probabilistic analysis of multiple Quick Select. Algorithmica 22, 569–584.Google Scholar
Mahmoud, H. M., Modarres, R. and Smythe, R. T. (1995). Analysis of Quickselect: an algorithm for order statistics. RAIRO Inf. Théor. Appl. 29, 255–276.Google Scholar
Paulsen, V. (1997). The moments of FIND. J. Appl. Prob. 34, 1079–1082.Google Scholar
Prodinger, H. (1995). Multiple Quickselect—Hoare's Find algorithm for several elements. Inform. Process. Lett. 56, 123–129.CrossRefGoogle Scholar
Régnier, M. (1989). A limiting distribution of quicksort. RAIRO Inf. Théor. Appl. 23, 335–343.CrossRefGoogle Scholar
Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Inf. Théor. Appl. 25, 85–100.Google Scholar
Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29, 3–33.CrossRefGoogle Scholar
Ross, S. (2002). A First Course in Probability, 6th edn. Prentice-Hall, Upper Saddle River, NJ.Google Scholar
Vallée, B., Clément, J., Fill, J. A. and Flajolet, P. (2009). The number of symbol comparisons in QuickSort and QuickSelect. In Automata, Languages and Programming (Lecture Notes Comput. Sci. 5555), Part I, Springer, Berlin, pp. 750–763.Google Scholar