MULTIPLE QUICKSELECT —

HOARE’S FIND ALGORITHM FOR SEVERAL ELEMENTS

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

Abstract. Hoare’s Find algorithm can be used to select p specified order statistics j_{1}, j_{2}, …, j_{p} from a file of n elements simultaneously. We give precise formulæ for both the average number of passes and the average number of comparisons. Averaging again over all possible subsets of p elements, we get results of Lent and Mahmoud as corollaries.

— April 26, 1996 —

1. Introduction

Hoare’s Find algorithm [3] uses the idea of Quicksort [5] in order to select the jth element of a file of n elements. In each partitioning step, a certain element will be brought into its correct position k. In the process, elements are moved—those brought to the left of it are smaller, and those brought to the right are larger. If k = j, the element is found; if k < j, one has to continue on the right side, searching for the (j − k)th element; if k > j, one has to continue on the left side, still searching for the jth element.

Two parameters are of interest: the (average) number of passes (recursive calls) P [n; j] and the (average) number of comparisons C[n; j]. In Knuth’s book [5] we already find the values

P [n; j] = H_{j} + H_{n+1−j} − 1

and

C[n; j] = 2(n + 3 + (n + 1)H_{n} − (j + 2)H_{j} − (n + 3 − j)H_{n+1−j})

where H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n} denotes the nth harmonic number; compare also [6] and [8]. In [4], this analysis was extended to the case of median–of–three partitioning. Hoare’s idea can be extended as follows: Assume that we simultaneously search for the

p elements with ranks j_{1}, j_{2}, …, j_{p} where 1 ≤ j_{1} < j_{2} < ⋯ < j_{p} ≤ n is a fixed set of p values. Then, according into which interval of the values j_{1}, …, j_{p} the pivot element falls, we may have found one of the elements and/or have to continue on both sides, but with

Typeset by AMS-TEX

File: lint3.tex

smaller sets. The idea is quite simple; a nice description of the algorithm can be found in [7].

Multiple Quickselect is also easy to code and behaves very well in all cases in practice— as the theoretical analysis predicts.

In the following we will give explicit formulæ for both the average number of passes P [n; j_{1}, …, j_{p}] and the average number of comparisons, C[n; j_{1}, …, j_{p}]. Also of interest are the grand averages,

P_{n,p} = \frac{1}{\binom{n}{p}} ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} P [n; j_{1}, …, j_{p}]

and

C_{n,p} = \frac{1}{\binom{n}{p}} ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} C[n; j_{1}, …, j_{p}] .

They were already considered in [7], and our explicit formulæ extend the asymptotic formulæ therein.

2. The average number of passes

We will give the recursion in the case of a two element set {j < l}. The general case is a straightforward extension which we omit as the formula is quite involved;

P [n; j, l] = 1 + \frac{1}{n} ∑_{1≤k<j} P [n − k; j − k, l − k]

+ \frac{1}{n} ∑_{j<k≤l} P [k − 1; j] + \frac{1}{n} ∑_{j≤k<l} P [n − k; l − k]

+ \frac{1}{n} ∑_{l<k≤n} P [k − 1; j, l] .

The extra 1 counts one pass of the algorithm, and the factor \frac{1}{n} is the probability that the kth element was chosen as a pivot element. If k is smaller than j or larger than l, we still search for two elements on one side, otherwise we search for one element on each side (unless we already found one of them; the case k = j of k = l).

Theorem 1.

P [n; j_{1}, …, j_{p}] = H_{j_{1}} + H_{n+1−j_{p}} + 2 ∑_{t=2}^{p} H_{j_{t}+1−j_{t−1}} − 2p + 1 . ♢

We don’t give a full proof of this theorem, because it is long and completely routine. The proof just shows that the given explicit formula fulfills the recursion, so that the result is proved by induction. Not more is required for that than the formula

∑_{1≤k<n} H_{k} = n(H_{n} − 1) .

It is however not all that easy to find the formula. The formula was guessed and verified through extensive computer experiments with the computer algebra system Maple.

Another line of proving the theorem, as suggested to us by C. Martínez, would be to work with generating functions. For instance

∑_{1≤j≤n}P [n; j]u^{j}z^{n}

= \frac{1}{1 − uz} log \frac{1}{1 − uz} + \frac{u}{(1 − uz)(1 − z)} log \frac{1}{1 − z} − \frac{uz}{(1 − z)(1 − uz)} .

And it is equally sufficient to show that this function fulfills the differential equation which is the equivalent in terms of generating functions to the recursion for the P [n; j]’s. In the general case, variables u_{1}, …, u_{p} and z must be used.

It might be instructive to give the special case of two elements explicitly:

P [n; j, l] = H_{j} + 2H_{l+1−j} + H_{n+1−l} − 3 .

Observe that this formula (as well as the general one) fulfills the identity P [n; j, l] = P [n; n + 1 − l, n + 1 − j], which is obvious from the symmetry of the algorithm.

To get some feeling about the average number of passes, let us assume that j_{t} ∼ a_{t} · n, with some constants 0 < a_{1} < ⋯ < a_{p} < 1, where p is fixed. Then

P [n; j_{1}, …, j_{p}] = 2p log n + O(1) .

It is also worth noticing that the formula for P [n; j_{1}, …, j_{p}] remains correct if we relax the condition 1 ≤ j_{1} < j_{2} < ⋯ < j_{p} ≤ n to 1 ≤ j_{1} ≤ j_{2} ≤ ⋯ ≤ j_{p} ≤ n.

If p = n, this just means sorting, and our formula tells us

P [n; 1, 2, …, n] = n,

which is well known (and obvious!); it comes out for instance from the recursion

P_{n} = 1 + \frac{1}{n} ∑_{k=1}^{n} (P_{k−1} + P_{n−k}) .

3. The average number of comparisons

The recursion for the number of comparisons is almost the same as before, except that the additional 1 (counting one pass) is now replaced by n − 1 which is the number of comparisons required to bring the kth element into its correct position. Let us again consider the case of a two element set {j < l},

C[n; j, l] = n − 1 + \frac{1}{n} ∑_{1≤k<j} C[n − k; j − k, l − k]

+ \frac{1}{n} ∑_{j<k≤l} C[k − 1; j] + \frac{1}{n} ∑_{j≤k<l} C[n − k; l − k]

+ \frac{1}{n} ∑_{l<k≤n} C[k − 1; j, l] .

Observe that we only count the comparisons which are necessary to bring the pivot element into its correct position k. Extra comparisons of k with the numbers j_{1}, …, j_{p} are not considered. (This would give an additional contribution of roughly log p comparisons.)

Theorem 2.

C[n; j_{1}, …, j_{p}] = 2n + j_{p} − j_{1} + 2(n + 1)H_{n} − 2(j_{1} + 2)H_{j_{1}} − 2(n + 3 − j_{p})H_{n+1−j_{p}}

− 2 ∑_{t=2}^{p}(j_{t} + 4 − j_{t−1})H_{j_{t}+1−j_{t−1}} + 8p − 2 . ♢

In this instance it is even more true that the finding of the formula is the nontrivial and the proof by induction is the routine part (which we therefore skip). It requires additionally the formula

∑_{1≤k<n} k H_{k} = \binom{n}{2}(H_{n} − \frac{1}{2}) .

The formula in Theorem 2 fulfills the required symmetry C[n; j_{1}, …, j_{p}] = C[n; n + 1 − j_{p}, …, n + 1 − j_{1}] and remains valid if some of the j’s are equal.

Again, if we let j_{t} ∼ a_{t} · n, we get

C[n; j_{1}, …, j_{p}] = n · [2 + a_{p} − a_{1} − 2a_{1} log a_{1} − 2(1 − a_{p}) log(1 − a_{p})

− 2 ∑_{t=2}^{p}(a_{t} − a_{t−1}) log(a_{t} − a_{t−1})] + O(log n) .

It is interesting to investigate when the factor of n gets maximal. For instance, in the case of two elements we see

a_{1} = \frac{1}{2 + \sqrt{e}} , a_{2} = 1 − a_{1} ;

for three elements we find

a_{1} = a_{3} = \frac{1}{2} · \frac{1 + 2\sqrt{e}}{1 + \sqrt{e}} , a_{2} = \frac{1}{2} ,

etc. If p = n, this just means sorting, and our formula tells us

C[n; 1, 2, …, n] = 2(n + 1)H_{n} − 4n ,

which is well known; it comes out for instance from the recursion

C_{n} = n − 1 + \frac{1}{n} ∑_{k=1}^{n} (C_{k−1} + C_{n−k}) .

Remark. Our explicit formulæ translate directly into the costs of the computation of several classes of (order–)statistics, such as e.g. the Hodges–Lehmann statistics. We merely give this general remark and refer to [7] and [9].

4. The grand average of passes

As we have already announced, we compute

∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} P [n; j_{1}, …, j_{p}] .

To achieve this goal, we first compute

∑_{1≤k≤n} H_{k}\binom{n − k}{p − 1} = [z^{n}]\frac{1}{1 − z} log \frac{1}{1 − z} · \frac{z^{p−1}}{(1 − z)^{p}}

= [z^{n+1−p}]\frac{1}{(1 − z)^{p+1}} log \frac{1}{1 − z}

= \binom{n + 1}{p} (H_{n+1} − H_{p}) .

Here, we used some generating functions that are discussed in great detail in [1] and [2]. Then we see

∑_{1≤j_{1}<···<j_{p}≤n} H_{j_{1}} = ∑_{1≤j≤n} H_{j}\binom{n − j}{p − 1}

= \binom{n + 1}{p} (H_{n+1} − H_{p}) = ∑_{1≤j_{1}<···<j_{p}≤n} H_{n+1−j_{p}}

and

∑_{t=2}^{p} ∑_{1≤j_{1}<···<j_{p}≤n} H_{j_{t}+1−j_{t−1}} = ∑_{1≤j<l≤n} H_{l+1−j}\binom{n − (l + 1 − j)}{p − 2}

= ∑_{k=2}^{n} H_{k}(n + 1 − k)\binom{n − k}{p − 2}

= (p − 1) ∑_{k=2}^{n} H_{k}\binom{n + 1 − k}{p − 1}

= (p − 1) ∑_{k=1}^{n+1} H_{k}\binom{n + 1 − k}{p − 1} − (p − 1)\binom{n}{p − 1}

= (p − 1)\binom{n + 2}{p} (H_{n+2} − H_{p}) − (p − 1)\binom{n}{p − 1} .

Collecting all contributions and dividing by \binom{n}{p}, we get Theorem 3.

P_{n,p} = \frac{2p(n + 1)^{2}}{(n + 2 − p)(n + 1 − p)}(H_{n+1} − H_{p}) + 1 − 2p − \frac{2(p − 1)^{2}}{n + 2 − p} . ♢

The classical case is p = 1, and then

P_{n,1} = 2(1 + \frac{1}{n})H_{n} − 3 .

Computing an asymptotic equivalent, we get Corollary 1. For p fixed and n → ∞ we have

P_{n,p} = 2pH_{n} − 2pH_{p} − 2p + 1 + 2p(2p − 1)\frac{H_{n}}{n}

− \frac{2p(2p − 1)H_{p} + 2(p^{2} − 3p + 1)}{n} + O(\frac{log n}{n^{2}}) .

5. The grand average of comparisons

For this, we need the following auxiliary results: Sum 1.

∑_{1≤j_{1}<···<j_{p}≤n}(j_{p} − j_{1}) = ∑_{1≤j<l≤n}(l − j)\binom{l − 1 − j}{p − 2}

= (p − 1) ∑_{1≤j<l≤n} \binom{l − j}{p − 1}

= (p − 1) ∑_{1≤k≤n} \binom{k}{p − 1}(n − k)

= (p − 1)\binom{n + 1}{p + 1} .

Sum 2.

∑_{1≤j_{1}<···<j_{p}≤n}(j_{1} + 2)H_{j_{1}} = ∑_{j=1}^{n}(j + 2)H_{j}\binom{n − j}{p − 1}

= ∑_{j=1}^{n} [(n + 3) − (n + 1 − j)]H_{j}\binom{n − j}{p − 1}

= (n + 3) ∑_{j=1}^{n} H_{j}\binom{n − j}{p − 1} − p ∑_{j=1}^{n+1} H_{j}\binom{n + 1 − j}{p}

= (n + 3)\binom{n + 1}{p}(H_{n+1} − H_{p}) − p\binom{n + 2}{p + 1}(H_{n+2} − H_{p+1})

= ∑_{1≤j_{1}<···<j_{p}≤n}(n + 3 − j_{p})H_{j_{p}} .

Sum 3.

∑_{t=2}^{p} ∑_{1≤j_{1}<···<j_{p}≤n}(j_{t} + 4 − j_{t−1})H_{j_{t}+1−j_{t−1}}

= ∑_{1≤j<l≤n}(l + 4 − j)H_{l+1−j}\binom{n − (l + 1 − j)}{p − 2}

= (p − 1)(n + 5)\binom{n + 2}{p}(H_{n+2} − H_{p})

− (p − 1)p\binom{n + 3}{p + 1}(H_{n+3} − H_{p+1}) − 4(p − 1)\binom{n}{p − 1} .

Now we collect all contributions and divide by \binom{n}{p} and, after several simplifications, we obtain the following explicit formula.

Theorem 4.

C_{n,p} = \frac{1}{(n + 2 − p)(n + 1 − p)}[(2H_{p} + 1)n^{3} − 8pH_{n}n^{2} + 4((p + 2)H_{p} + p)n^{2}
+ 2p(p − 9)H_{n}n + (−5p^{2} + p − 1 + 2(4p + 5)H_{p})n
+ 2p(p − 5)H_{n} + 4(p + 1)H_{p} − p(p + 7)] . ♢

The classical case is p = 1, and then

C_{n,1} = 3n − 8H_{n} + 13 − \frac{8H_{n}}{n} .

Computing an asymptotic equivalent, we get Corollary 2. For p fixed and n → ∞ we have

C_{n,p} = (2H_{p} + 1)n − 8pH_{n} + 2(4p + 1)H_{p} + 3(2p − 1) − 2p(7p − 3)\frac{H_{n}}{n}

+ \frac{2p(7p − 3)H_{p} + 2(p − 3)(3p − 1)}{n} + O(\frac{log n}{n^{2}}) .

Acknowledgment. I thank Prof. H. Mahmoud for sending me his preprint and clarifying some of the ideas therein as well as Prof. C. Martínez for interesting suggestions. Comments of two referees helped to improve the presentation of the paper.

References

1. R. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

2. D. Greene, D.E. Knuth, Mathematics for the Analysis of Algorithms, Birkhäuser, 1981.

3. C.A.R. Hoare, Find (Algorithm 65), Comm. of the ACM 4 (1961), 321–222.

4. P. Kirschenhofer, C. Martínez, and H. Prodinger, Analysis of Hoare’s Find algorithm with median– of–three partition, submitted (1995).

5. D.E. Knuth, The Art of Computer Programming Vol. 3, Addison–Wesley, Reading, MA, 1973.

6. D.E. Knuth, Mathematical analysis of algorithms, Proc. of the 1971 IFIP Congress (1971), 19–27.

7. J. Lent and H. Mahmoud, Average–case analysis of multiple quickselect: An algorithm for finding order statistics, Statistics and Probability Letters (1995) (to appear).

8. M. Mahmoud, R. Modarres, and R. Smythe, Analysis of Quickselect: an algorithm for order statistics, RAIRO, Theoretical Informatics and Applications (1995) (to appear).

9. R. Serfling, Approximation Theories of Mathematical Statistics, Wiley, 1980.

TU Vienna Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: proding@rsmb.tuwien.ac.at