Randomized Quicksort and the Entropy of the Random Source

Algebraic Methods in Computational Complexity

计算机科学;物理学;物理学

Beatrice List ; Markus Maucher ; Uwe Scho¨ning ; Rainer Schuler

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/104/pdf/04421.MaucherMarkus1.Paper.104.pdf
PID  :  6467

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

The worst-case complexity of an implementation of Quick-sort depends on the random number generator that is used to select the pivot elements. In this paper we estimate the expected number of com- parisons 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 logn to n2, 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.