The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off

References

  • Bindjeme, Patrick; Fill, James Allen. The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract), Proceedings of the 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, 2012, to appear, available from http://www.ams.jhu.edu/~fill/.
  • Chung, Kai Lai. A Course in Probability Theory. Third edition. Academic Press, Inc., San Diego, CA, 2001. xviii+419 pp. ISBN: 0-12-174151-6 MR1796326
  • Dongarra, Jack; Sullivan, Francis. Guest editors' introduction: the top 10 algorithms, Computing in Science & Engineering 2 (2000), no. 1, 22--23.
  • Fill, James Allen. Distributional convergence for the number of symbol comparisons used by QuickSort, Annals of Applied Probability (2012, to appear, available from http://www.ams.jhu.edu/~fill/).
  • Fill, James Allen; Janson, Svante. Smoothness and decay properties of the limiting Quicksort density function. Mathematics and computer science (Versailles, 2000), 53--64, Trends Math., Birkhäuser, Basel, 2000. MR1798287
  • Fill, James Allen; Janson, Svante. Quicksort asymptotics. Analysis of algorithms. J. Algorithms 44 (2002), no. 1, 4--28. MR1932675
  • Fill, James Allen; Janson, Svante. The number of bit comparisons used by Quicksort: an average-case analysis, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (New York), ACM, 2004, pp. 300--307 (electronic). MR2291065
  • Fill, James Allen; Nakama, Takéhiko. Analysis of the expected number of bit comparisons required by Quickselect. Algorithmica 58 (2010), no. 3, 730--769. MR2672478
  • Fill, James Allen; Nakama, Takéhiko. Distributional convergence for the number of symbol comparisons used by QuickSelect, Preprint available from available from http://www.ams.jhu.edu/~fill/, 2012.
  • Flajolet, Philippe; Gourdon, Xavier; Dumas, Philippe. Mellin transforms and asymptotics: harmonic sums. Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3--58. MR1337752
  • Flajolet, Philippe; Sedgewick, Robert. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009. xiv+810 pp. ISBN: 978-0-521-89806-5 MR2483235
  • Gut, Allan. Probability: A Graduate Course. Springer Texts in Statistics. Springer, New York, 2005. xxiv+603 pp. ISBN: 0-387-22833-0 MR2125120
  • Hoare, C. A. R. Quicksort. Comput. J. 5 1962 10--15. MR0142216
  • Knessl, Charles; Szpankowski, Wojciech. Quicksort algorithm again revisited. Discrete Math. Theor. Comput. Sci. 3 (1999), no. 2, 43--63 (electronic). MR1685649
  • Knuth, Donald Ervin. The Art of Computer Programming. Vol. 3: Sorting and Searching, second ed., Addison-Wesley, 1998.
  • Mahmoud, Hosam M. Evolution of Random Search Trees. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xii+324 pp. ISBN: 0-471-53228-2 MR1140708
  • Neininger, Ralph; Rüschendorf, Ludger. Rates of convergence for Quicksort. Analysis of algorithms. J. Algorithms 44 (2002), no. 1, 51--62. MR1932677
  • Régnier, Mireille. A limiting distribution for quicksort. RAIRO Inform. Théor. Appl. 23 (1989), no. 3, 335--343. MR1020478
  • Rosenthal, Haskell P. On the subspaces of $L^{p}$ $(p>2)$ spanned by sequences of independent random variables. Israel J. Math. 8 1970 273--303. MR0271721
  • Rösler, Uwe. A limit theorem for "Quicksort''. RAIRO Inform. Théor. Appl. 25 (1991), no. 1, 85--100. MR1104413
  • Roura, Salvador. Digital access to comparison-based tree data structures and algorithms. J. Algorithms 40 (2001), no. 1, 1--23. MR1841250
  • Vallée, Brigitte; Clément, Julien; Fill, James Allen; Flajolet, Philippe. The number of symbol comparisons in QuickSort and QuickSelect, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 5555, Springer, Berlin, 2009, pp. 750--763. MR2544890 (2012b:68231)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.