Towards a Realistic Analysis of the QuickSelect Algorithm

摘要

We revisit the analysis of the classical QuickSelect algorithm. Usually, the analysis deals with the mean number of key comparisons, but here we view keys as words produced by a source, and words are compared via their symbols in lexicographic order. 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. The "realistic" cost of the algorithm is here the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons. For the QuickSort algorithm, known average-case complexity results are of in the case of key comparisons, and for symbol comparisons. For QuickSelect algorithms, and with respect to key comparisons, the average-case complexity is I similar to(n). In this present article, we prove that, with respect to symbol comparisons, QuickSelect's average-case complexity remains I similar to(n). In each case, we provide explicit expressions for the dominant constants, closely related to the probabilistic behaviour of the source.