Comparisons in Hoare's FIND algorithm
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.
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)