Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
The Number of Symbol Comparisons in QuickSort and QuickSelect
verfasst von : Brigitte Vallée, Julien Clément, James Allen Fill, Philippe Flajolet
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We revisit the classical
QuickSort
and
QuickSelect
algorithms, under a complexity model that fully takes into account the elementary comparisons between symbols composing the records to be processed. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. We establish that, under our conditions, the average-case complexity of
QuickSort
is
O
(
n
log
2
n
) [rather than
O
(
n
log
n
), classically], whereas that of
QuickSelect
remains
O
(
n
). Explicit expressions for the implied constants are provided by our combinatorial–analytic methods.