Randomized Quicksort and the Entropy of the Random Source
The worst-case complexity of an implementation of Quicksort depends on the random source that is used to select the pivot elements. In this paper we estimate the expected number of comparisons of Quicksort as a function of 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 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, as well as an upper bound when using a δ-random source.
Quicksort Randomized Algorithms Entropy
Beatrice List Markus Maucher Uwe Schoning Rainer Schuler
Abt. Theoretische Informatik, Universitat Uhn, 89069 Ulm, Germany
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
450-460
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）