A characterization of the set of fixed points of the Quicksort transformation

The limiting distribution $\mu$ of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation $T$ - unique, that is, subject to the constraints of zero mean and finite variance. We show that a distribution is a fixed point of $T$ if and only if it is the convolution of $\mu$ with a Cauchy distribution of arbitrary center and scale. In particular, therefore, $\mu$ is the unique fixed point of $T$ having zero mean.

• Publication year

  2000

• Venue

  arXiv.org

• Publication date

  2000-05-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/ECP.V5-1021arXiv math/0005236
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Smoothness and decay properties of the limiting Quicksort density function

  2000cited by this paper
• Quicksort Algorithm Again Revisited

  1999cited by this paper
• The Contraction Method for Recursive Algorithms

  1999cited by this paper
• A Limit Theorem for "quicksort"

  1999influential reference
• A Fixed Point Theorem for Distributions

  1999cited by this paper
• Fixed points of a generalized smoothing transformation and applications to the branching random walk

  1998cited by this paper
• A fixed point theorem for distributions

  1992cited by this paper
• Sur une extension de la notion de loi semi-stable

  1990cited by this paper
• Fixed points of the smoothing transformation

  1983cited by this paper
• A Course in Probability Theory

  1949cited by this paper

• Probabilistic analysis of optimal multi-pivot QuickSort

  2025cites this paper
• A Necessary and Sufficient Condition for the Tail-Triviality of a Recursive Tree Process

  2022cites this paper
• Almost sure convergence to the Quicksort process

  2020cites this paper
• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)

  2019cites this paper
• Stochastic fixed-point equations

  2019cites this paper
• All solutions of the stochastic fixed point equation of the Quicksort process

  2018cites this paper
• On the Tails of the Limiting QuickSort Density

  2018cites this paper
• 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018, Uppsala, Sweden, June 25-29, 2018

  2018cites this paper
• The Weighted Branching Process

  2016cites this paper
• Process convergence for the complexity of Radix Selection on Markov sources

  2016influential citation
• Application of fixed point theorem in probabilistic metric space to quicksort algorithm

  2015cites this paper
• On the tails of the limiting Quicksort distribution

  2015cites this paper
• Belief Propagation and Algorithms for Mean-Field Combinatorial Optimisations

  2014cites this paper
• The Quicksort process

  2013cites this paper
• Distributional convergence for the number of symbol comparisons used by QuickSort

  2012cites this paper
• Endogeny for the Logistic Recursive Distributional Equation

  2011cites this paper
• Fixed points of the smoothing transform: two-sided solutions

  2010influential citation
• Lösungen inhomogener stochastischer Fixpunktgleichungen

  2010influential citation
• Gamma‐Ray Spectroscopy at TRIUMF‐ISAC: the New Frontier of Radioactive Ion Beam Research

  2009cites this paper
• On stochastic recursive equations of sum and max type

  2006cites this paper
• Probabilistic analysis of algorithms , stochastic fixed-point equations and ideal metrics

  2006cites this paper
• The size of random fragmentation trees

  2006influential citation
• Bivariate Uniqueness and Endogeny for the Logistic Recursive Distributional Equation

  2004cites this paper
• Stochastische Analyse von Algorithmen, Fixpunktgleichungen und ideale Metriken

  2004cites this paper
• A survey of max-type recursive distributional equations

  2004cites this paper
• Bivariate Uniqueness and Endogeny for Recursive Distributional Equations : Two Examples

  2004cites this paper
• Max-type Recursive Distributional Equations

  2003cites this paper
• The Weighted Branching Process and Its Associated Stochastic Fixed Point Equation

  2003cites this paper
• On fixed points of Poisson shot noise transforms

  2002cites this paper
• Rates of convergence for Quicksort

  2002cites this paper
• Quicksort asymptotics

  2001cites this paper
• Approximating the Limiting Qui ksort

  2001cites this paper
• Approximating the limiting Quicksort distribution

  2001cites this paper
• Approximations ofthe Limiting Quicksort Distribution ( SECOND DRAFT )

  2000cites this paper