2026-07-23T00:23:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:104 2024-03-06T11:06:00Z ddc:004 open_access

Randomized QuickSort and the Entropy of the Random Source List, Beatrice Maucher, Markus Schöning, Uwe Schuler, Rainer Randomized Algorithms QuickSort Entropy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Beatrice List and Markus Maucher and Uwe Schöning and Rainer Schuler 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.04421.5 urn:nbn:de:0030-drops-1043 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.5 eng https://creativecommons.org/licenses/by/4.0/legalcode