Distributional convergence for the number of symbol comparisons used by QuickSelect (Q2837754)

The article contains an in-depth analysis of QuickSelect, the classic algorithm (described by \textit{C. A. R.\ Hoare} in [``Algorithm 65: Find'', Commun. ACM 4, No. 7, 321--322 (1961; \url{doi:10.1145/366622.366647})]) to select an element with a given rank in an unordered file of elements. It is similar to QuickSort but stops the search if the current pivot element has the desired rank and continues only in the subset of remaining elements that may have the appropriate rank (different from QuickSort that continues in both parts).NEWLINENEWLINEThe algorithm has already been subject of detailed studies and precise results are known about the number of key comparisons needed and sufficient to locate the desired element. In this article the analysis is made more intricate and detailed by taking into account the cost of key comparisons under the assumption that keys are sequences of symbols from a finite alphabet. The analysis is carried out for randomly generated keys under the assumption that the keys are generated independently and identically distributed, and using continuous distributions so that the keys can be assumed to be all distinct. Three types of random key sources are considered, namely memoryless sources, Markov sources and intermittent sources.