×

On the number of comparisons in Hoare’s algorithm “FIND”. (English) Zbl 0910.60002

Summary: In 1961 Hoare gave an extremely simple algorithm for finding the median from a list of size \(n\). That algorithm was later investigated by Knuth, who derived a closed form expression for the expected number of comparisons. In the present paper we show that the (random) number of comparisons, divided by \(n\), has a limit distribution as \(n\to\infty\), and the rate of convergence measured in Wasserstein metric is \(\Theta(\log n/n)\), while using other probabilistic distances, such as \(\Phi\)-average compound distances with convex Young functions \(\Phi\), the rate of convergence is \(\Theta(1/n)\).

MSC:

60F05 Central limit and other weak theorems
68P10 Searching and sorting
PDFBibTeX XMLCite