The Number of Symbol Comparisons in QuickSort and QuickSelect
2009; Springer Science+Business Media; Linguagem: Inglês
10.1007/978-3-642-02927-1_62
ISSN1611-3349
AutoresBrigitte Vallée, Julien Clément, James Allen Fill, Philippe Flajolet,
Tópico(s)Advanced Image and Video Retrieval Techniques
ResumoWe 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(nlog2 n) [rather than O(nlogn), classically], whereas that of QuickSelect remains O(n). Explicit expressions for the implied constants are provided by our combinatorial–analytic methods.
Referência(s)