1 Search Results for "Maucher, Markus"

Document
DOI: 10.4230/DagSemProc.04421.5
Randomized QuickSort and the Entropy of the Random Source

Authors: Beatrice List, Markus Maucher, Uwe Schöning, and Rainer Schuler

Published in: Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{list_et_al:DagSemProc.04421.5,
  author =	{List, Beatrice and Maucher, Markus and Sch\"{o}ning, Uwe and Schuler, Rainer},
  title =	{{Randomized QuickSort and the Entropy of the Random Source}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.5},
  URN =		{urn:nbn:de:0030-drops-1043},
  doi =		{10.4230/DagSemProc.04421.5},
  annote =	{Keywords: Randomized Algorithms , QuickSort , Entropy}
}
  • Refine by Author
  • 1 List, Beatrice
  • 1 Maucher, Markus
  • 1 Schuler, Rainer
  • 1 Schöning, Uwe

  • Refine by Classification

  • Refine by Keyword
  • 1 Entropy
  • 1 QuickSort
  • 1 Randomized Algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2005

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact