Skip to main content
Springer Nature Link
Log in

Smoothness and Decay Properties of the Limiting Quicksort Density Function

  • Conference paper
Mathematics and Computer Science

Part of the book series: Trends in Mathematics ((TM))

  • 509 Accesses

Abstract

Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and infinitely differentiable density f, and that each derivative f (k) enjoys superpolynomial decay at ±∞. In particular, each f (k) is bounded. Our method is sufficiently computational to prove, for example, that f is bounded by 16.

1Research supported by NSF grant DMS-9803780, and by the Acheson J. Duncan Fund for the Advancement of Research in Statistics.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) // springerPlus roll out starts here if (window.localStorage) { window.localStorage.removeItem("springerPlusRollOut") } //springerPlus ends here var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth <= buyboxMaxSingleColumnWidth && option != buyingOption) { hideBuyingOption(option) } }) var expanded = toggle.getAttribute("aria-expanded") === "true" || false toggle.setAttribute("aria-expanded", !expanded) form.hidden = expanded if (!expanded) { buyingOption.classList.add("expanded") } else { buyingOption.classList.remove("expanded") } priceInfo.hidden = expanded }, false) } } function hideBuyingOption(buyingOption) { var toggle = buyingOption.querySelector(".buying-option-price") var form = buyingOption.querySelector(".buying-option-form") var priceInfo = buyingOption.querySelector(".price-info") toggle.setAttribute("aria-expanded", false) form.hidden = true buyingOption.classList.remove("expanded") priceInfo.hidden = true } function initKeyControls() { document.addEventListener("keydown", function (event) { if (document.activeElement.classList.contains("buying-option-price") && (event.code === "Space" || event.code === "Enter")) { if (document.activeElement) { event.preventDefault() document.activeElement.click() } } }, false) } function initialStateOpen() { var buyboxWidth = buybox.offsetWidth ;[].slice.call(buybox.querySelectorAll(".buying-option")).forEach(function (option, index) { var toggle = option.querySelector(".buying-option-price") var form = option.querySelector(".buying-option-form") var priceInfo = option.querySelector(".price-info") if (buyboxWidth > buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. van der Corput, J. G. Zahlentheoretische Abschätzungen. Math. Ann. 84 (1921), 53–79.

    Article  MathSciNet  MATH  Google Scholar 

  2. Eddy, W. F. and Schervish, M. J. How many comparisons does Quicksort use? J. Algorithms 19 (1995), 402–431.

    Article  MathSciNet  MATH  Google Scholar 

  3. Feller, W. An Introduction to Probability Theory and its Applications. Vol. II. Second edition. Wiley, New York, 1971.

    MATH  Google Scholar 

  4. Flajolet, Ph. See http://algo.inria.fr/AofA/Research/05-99.html/AofA/Research/05-99.html.

  5. Hennequin, P. Combinatorial analysis of quicksort algorithm. RAIRO Inform. Théor. Appl. 23 (1989), 317–333.

    MathSciNet  MATH  Google Scholar 

  6. Hennequin, P. Analyse en moyenne d’algorithmes, tri rapide et arbres de recherche. Ph.D. dissertation, L’École Polytechnique Palaiseau.

    Google Scholar 

  7. Hoare, C. A. R. Quicksort. Comput. J 5 (1962), 10–15.

    Article  MathSciNet  MATH  Google Scholar 

  8. Knessl, C. and Szpankowski, W. Quicksort algorithm again revisited. Discrete Math. Theor. Comput. Sci 3 (1999), 43–64.

    MATH  Google Scholar 

  9. Knuth, D. E. The Art of Computer Programming. Volume 3. Sorting and searching Second edition. Addison—Wesley, Reading, Mass., 1998.

    Google Scholar 

  10. Montgomery, H. L. Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis. CBMS Reg. Conf. Ser. Math. 84, AMS, Providence, R.I., 1994.

    MATH  Google Scholar 

  11. Régnier, M. A limiting distribution for quicksort. RAIRO Inform. Th é or. Appl 23 (1989), 335–343.

    MathSciNet  MATH  Google Scholar 

  12. Rösier, U. A limit theorem for ‘Quicksort’. RAIRO Inform. Th é or. Appl 25 (1991), 85–100.

    MathSciNet  Google Scholar 

  13. Rudin, W. Functional Analysis Second edition. McGraw—Hill, New York, 1991.

    MATH  Google Scholar 

  14. Schwartz, L. Th é orie des Distributions Second edition. Hermann, Paris, 1966.

    MATH  Google Scholar 

  15. Tan, K. H. and Hadjicostas, P. Some properties of a limiting distribution in Quicksort. Statist. Probab. Lett 25 (1995), 87–94.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, The Johns Hopkins University, USA

    James Allen Fill

  2. Department of Mathematics, Uppsala University, Sweden

    Svante Janson

Authors
  1. James Allen Fill
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Svante Janson
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Bâtiment Descartes, Université de Versailles-St-Quentin PRISM, 45 avenue des Etats-Unis, 78035, Versailles, Cedex, France

    Danièle Gardy

  2. Département de Mathématiques Bâtiment Fermat, Université de Versailles-St-Quentin, 45 avenue des Etats-Unis, 78035, Versailles, Cedex, France

    Abdelkader Mokkadem

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer Basel AG

About this paper

Cite this paper

Fill, J.A., Janson, S. (2000). Smoothness and Decay Properties of the Limiting Quicksort Density Function. In: Gardy, D., Mokkadem, A. (eds) Mathematics and Computer Science. Trends in Mathematics. Birkhäuser, Basel. https://doi.org/10.1007/978-3-0348-8405-1_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-0348-8405-1_5

  • Publisher Name: Birkhäuser, Basel

  • Print ISBN: 978-3-0348-9553-8

  • Online ISBN: 978-3-0348-8405-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation