Towards a Realistic Analysis of the QuickSelect Algorithm

详细信息    查看全文

• 作者：Julien Clément ; James Allen Fill ; Thu Hien Nguyen Thi…
• 关键词：Probabilistic analysis of algorithms ; Sorting and searching algorithms ; Selection problem ; Pattern matching ; Permutations ; Information theory ; Rice’s method ; Asymptotic estimates ; Quickselect
• 刊名：Theory of Computing Systems
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：58
• 期：4
• 页码：528-578
• 全文大小：1,480 KB
• 参考文献：1.Cénac, P., Chauvin, B., Paccaut, F., Pouyanne, N.: Uncommon suffix tries. Random Struct. Algoritm. (2013)
  2.Clément, J., Flajolet, P., Vallée, B.: Dynamical sources in information theory: a general analysis of trie structures. Algorithmica 29(1), 307–369 (2001)MathSciNet CrossRef MATH
  3.Clément, J., Nguyen Thi, T. H., Vallée, B.: A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 598–609. Dagstuhl, Germany (2013)
  4.Clément, J., Nguyen Thi, T. H., Vallée, B.: Towards a realistic analysis of some popular sorting algorithms. Special issue of CPC (Combinatorics, Probability and Computing) dedicated to Philippe Flajolet 24(01), 104–144 (2014)MathSciNet
  5.De Bruijn, N.: Asymptotic methods in analysis, Dover (1981)
  6.Fill, J., Matterer, J.: QuickSelect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case Find. To appear in the special issue of CPC dedicated to Philippe Flajolet (2014)
  7.Fill, J.A., Nakama, T.: Analysis of the expected number of bit comparisons required by QuickSelect. Algorithmica 58(3), 730–769 (2010)MathSciNet CrossRef MATH
  8.Fill, J.A., Nakama, T.: Distributional convergence for the number of symbol comparisons used by QuickSelect. Adv. Appl. Probab. 45, 425–450 (2013)MathSciNet CrossRef MATH
  9.Flajolet, P., Sedgewick, R.: Mellin transforms and asymptotics: finite differences and Rice’s integrals. Theor. Comput. Sci. 144(1&2), 101–124 (1995)MathSciNet CrossRef MATH
  10.Flajolet, P., Sedgewick, R.: Analytic combinatorics. Cambridge University Press (2009)
  11.Grabner, P.J., Prodinger, H.: On a constant arising in the analysis of bit comparisons in Quickselect. Quaestiones Mathematicae 31(4), 303–306 (2008)MathSciNet CrossRef MATH
  12.Hoare, C.A.R.: Algorithm 63: partition. Commun. ACM 4(7), 321 (1961)CrossRef
  13.Hoare, C.A.R.: Algorithm 64: Quicksort. Commun. ACM 4(7), 321 (1961)CrossRef
  14.Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10–15 (1962)MathSciNet CrossRef MATH
  15.Knuth, D.E.: Mathematical analysis of algorithms. In: IFIP Congress (1), pp 19–27 (1971)
  16.Knuth, D.E.: The art of computer programming, vol 3, 2nd edn. Sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City (1998)
  17.Mosteller, F.: On some useful inefficient statistics. Ann. Math. Statist. 17(4), 377–408 (1946)MathSciNet CrossRef MATH
  18.Nguyen Thi, T. H.: Towards a realistic analysis of sorting and searching algorithms. PhD thesis, Université de Caen Basse Normandie (2014)
  19.Nörlund, N.E.: Leçons sur les équations linéaires aux différences finies. Collection de monographies sur la théorie des fonctions, p 1929. Gauthier-Villars, Paris
  20.Nörlund, N.E.: Vorlesungen über Differenzenrechnung. Chelsea Publishing Company, New York (1954)
  21.Sedgewick, R.: Quicksort. Outstanding dissertations in the computer sciences. Garland Publishing, New York (1975)
  22.Sedgewick, R.: Quicksort. Garland Pub. Co., New York (1980)MATH
  23.Sedgewick, R., Flajolet, P.: An introduction to the analysis of algorithms. Addison-Wesley-Longman (1996)
  24.Seidel, R.: Data-specific analysis of string sorting. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, SODA, pp. 1278–1286 (2010)
  25.Vallée, B.: Dynamical sources in information theory: fundamental intervals and word prefixes. Algorithmica 29(1/2), 262–306 (2001)MathSciNet CrossRef MATH
  26.Vallée, B., Clément, J., Fill, J.A., Flajolet, P.: The number of symbol comparisons in QuickSort and QuickSelect. In: Albers, S., et al. (eds.) Proceedings of ICALP 2009, Part I, vol. 5555 of Lecture Notes in Computer Science, pp. 750–763. Springer (2009)
  27.van Emden, M.H.: Increasing the efficiency of quicksort. Commun. ACM 13(9), 563–567 (1970)CrossRef MATH
  
• 作者单位：Julien Clément (1)
  James Allen Fill (2)
  Thu Hien Nguyen Thi (1)
  Brigitte Vallée (1)
  
  1. GREYC, CNRS-UMR 6072, Université de Caen, ENSICAEN, 14032, Caen, France
  2. Department of Applied Mathematics and Statistics, The Johns Hopkins University, Baltimore, MD, 21218-2682, USA
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1433-0490

文摘

We revisit the analysis of the classical QuickSelect algorithm. Usually, the analysis deals with the mean number of key comparisons, but here we view keys as words produced by a source, and words are compared via their symbols in lexicographic order. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. The “realistic” cost of the algorithm is here the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons. For the QuickSort algorithm, known average-case complexity results are of \({\Theta } (n \log n)\) in the case of key comparisons, and \({\Theta }(n\log ^{2} n)\) for symbol comparisons. For QuickSelect algorithms, and with respect to key comparisons, the average-case complexity is Θ(n). In this present article, we prove that, with respect to symbol comparisons, QuickSelect’s average-case complexity remains Θ(n). In each case, we provide explicit expressions for the dominant constants, closely related to the probabilistic behaviour of the source.