A characterization of the set of fixed points of the Quicksort transformation
| dc.creator | Fill, James Allen | |
| dc.creator | Janson, Svante | |
| dc.date | 2000-05-23 | |
| dc.date.accessioned | 2026-07-07T04:35:29Z | |
| dc.date.available | 2026-07-07T04:35:29Z | |
| dc.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. | |
| dc.description | 9 pages. See also http://www.mts.jhu.edu/~fill/ and http://www.math.uu.se/~svante/papers . Submitted for publication in May,2000 | |
| dc.identifier | https://arxiv.org/abs/math/0005236 | |
| dc.identifier | http://arxiv.org/abs/math/0005236 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/59269 | |
| dc.subject | Probability | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | 68W40 (primary), 60E05, 60E10, 68P10 (secondary) | |
| dc.title | A characterization of the set of fixed points of the Quicksort transformation | |
| dc.type | text |