×

zbMATH — the first resource for mathematics

Comparisons in Hoare’s Find algorithm. (English) Zbl 0892.68021
Summary: We study the number of comparisons in Hoare’s Find algorithm. Using trivariate generating functions, we get an explicit expression for the variance of the number of comparisons, if we search for the \(j\)th element in a random permutation of \(n\) elements. The variance is also asymptotically evaluated under the assumption that \(j\) is proportional to \(n\). Similar results for the number of passes (recursive calls) are given, too.

MSC:
68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI