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

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

2000-05-23

arxiv.org/abs/math/0005236v1

Mathematics

Probability

9 pages. See also http://www.mts.jhu.edu/~fill/ and http://www.math.uu.se/~svante/papers . Submitted for publication in May,20

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A characterization of the set of fixed points of the Quicksort transformation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A characterization of the set of fixed points of the Quicksort transformation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A characterization of the set of fixed points of the Quicksort transformation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-99061