Comparisons in Hoare's FIND algorithm

Abstract. 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.

helmut@gauss.cam.wits.ac.za,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)