14h: The Number of Symbol Comparisons in QuickSort and QuickSelect. Brigitte Vallée, Université de Caen.

We revisit the classical QuickSort and QuickSelect algorithms, under a complexity model, which 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), Markov, as well as many unbounded-correlation sources. We establish that, under our conditions, the average-case complexity of QuickSort is $O(n\log^2n)$ [rather than~$O(n\log n)$, classically], whereas that of QuickSelect remains~$O(n)$. Precise explicit expressions for the implied constants are provided by our combinatorial--analytic methods. Joint work with Julien Cléement, James Allen Fill and Philippe Flajolet