License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1043
URL: http://drops.dagstuhl.de/opus/volltexte/2005/104/
List, Beatrice ; Maucher, Markus ; Schöning, Uwe ; Schuler, Rainer

Randomized QuickSort and the Entropy of the Random Source

pdf-format:
Dokument 1.pdf (209 KB)

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.

BibTeX - Entry

@InProceedings{list_et_al:DSP:2005:104,
  author =	{Beatrice List and Markus Maucher and Uwe Sch{\"o}ning and Rainer Schuler},
  title =	{Randomized QuickSort and the Entropy of the Random Source},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2005},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  number =	{04421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/104},
  annote =	{Keywords: Randomized Algorithms , QuickSort , Entropy}
}

Keywords: Randomized Algorithms , QuickSort , Entropy
Seminar: 04421 - Algebraic Methods in Computational Complexity
Issue date: 2005
Date of publication: 24.03.2005

DROPS-Home | Fulltext Search | Imprint Published by LZI