TR04-059 Authors: Beatrice List, Markus Maucher, Uwe SchÃ¶ning, Rainer Schuler

Publication: 16th July 2004 21:42

Downloads: 1995

Keywords:

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, the

geometrical distribution and the delta-random source.