A characterization of the set of fixed points of the Quicksort transformation
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
The limiting distribution μ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 μwith a Cauchy distribution of arbitrary center and scale. In particular, therefore, μis the unique fixed point of T having zero mean.
9 pages. See also http://www.mts.jhu.edu/~fill/ and http://www.math.uu.se/~svante/papers . Submitted for publication in May,2000
9 pages. See also http://www.mts.jhu.edu/~fill/ and http://www.math.uu.se/~svante/papers . Submitted for publication in May,2000