DagSemProc.04421.5.pdf
- Filesize: 209 kB
- 15 pages
Document
Randomized QuickSort and the Entropy of the Random Source
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 4421
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2005-03-24
Cite As Get BibTex
Beatrice List, Markus Maucher, Uwe Schöning, and Rainer Schuler. Randomized QuickSort and the Entropy of the Random Source. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.04421.5
Abstract
The worst-case complexity of an implementation of Quicksort depends on the random number generator that is used to select the pivot elements. In this paper we estimate the expected number of comparisons of Quicksort as a function in the entropy of the random source. We give upper and lower bounds and show that the expected number of comparisons increases from $n\log n$ to $n^2$, if the entropy of the random source is bounded. As examples we show explicit bounds for distributions with bounded min-entropy and the geometrical distribution.
Subject Classification
Keywords
- Randomized Algorithms
- QuickSort
- Entropy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads