Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Quicksort:
TR04-059 | 21st June 2004
Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

Randomized Quicksort and the Entropy of the Random Number Generator

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 ... more >>>

TR07-039 | 27th March 2007
Bodo Manthey, Till Tantau

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

Binary search trees are a fundamental data structure and their height
plays a key role in the analysis of divide-and-conquer algorithms like
quicksort. Their worst-case height is linear; their average height,
whose exact value is one of the best-studied problems in average-case
complexity, is logarithmic. We analyze their smoothed height ... more >>>

ISSN 1433-8092 | Imprint