9.7.3 Algorithm 3

Worst case linear time algorithm due to

Blum, Floyd, Pratt, Rivest, Tarzan.

REF.

Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, Volume 7, Number 4, pp. 448-461, 1973.

• This is also a variation of quicksort and the main idea is to find a good pivot.
• Assume that all the elements are distinct. The algorithm works otherwise too.

1.

Divide the n elements into groups of 5 leaving aside between 0 and 4 elements that cannot be placed in a group.

 

 

Sort each group of 5 elements by any algorithm and take the middle element from each group. This yields

                                                                                                        $\lfloor$n/5$\rfloor$ medians.

2.

Use the SELECT algorithm to find the median of these $\lfloor$n/5$\rfloor$elements. Choose this median as the pivot.

• Note that this pivot is in position $\lfloor$${\frac{n+5}{10}}$$\rfloor$
• Also, the pivot exceeds $\lfloor$${\frac{n-5}{10}}$$\rfloor$ of the middle elements and each of these middle elements exceeds two elements. Thus, the pivot exceeds at least 

                                                        3$$\lfloor$$$${\frac{n-5}{10}}$$$$\rfloor$$ elements.

Also, by a similar argument, the pivot is less than at least 
 
                                           3$$\lfloor$$$${\frac{n-5}{10}}$$$$\rfloor$$ elements.
• If n $\geq$ 75, 

                                        3$$\lfloor$$$${\frac{n-5}{10}}$$$$\rfloor$$$$\geq$$ 3$$\lfloor$$$${\textstyle\frac{70}{10}}$$$$\rfloor$$ = 21 > $${\textstyle\frac{75}{4}}$$

In other words, 

                            n$$\geq$$ 75 $$\Rightarrow$$ 3$$\left[\vphantom{\frac{n+5}{10}}\right.$$$${\frac{n+5}{10}}$$$$\left.\vphantom{\frac{n+5}{10}}\right]$$$$\geq$$$${\frac{n}{4}}$$

This would mean that, if n$\geq$ 75, the pivot is greater than at least ${\frac{n}{4}}$ elements and less than at least ${\frac{n}{4}}$ elements. Consequently, when we partition an array with this pivot, the k^th element is isolated to within a range of at most ${\frac{3n}{4}}$ of the elements.
 

Implementation

keytype select (int i, j, k);

        /* returns key of the k^th largest element among A[i]  ^...  A[j]*/

        {

            if((j - i) < 75)

                find the k^th largest by some simple algorithm

            else {

                for(m = 0;m$\leq$ (j - i - 4)/5;m + +)

            {

                find the third element among A[i + 5 * m]  ^...  A[i + 5 * m + 4]

                and swap it with A[i + m];

                pivot = select (i,(j - i - 4)/5,(j - i - 4)/10)

                m = partition (i, j, pivot);

                       if(k$\leq$m - i)

                            return (select (i, m - 1, k))

                     else

                            return (select (m, j,(k - (m - i)))

            }

        }

}

The worst case complexity of the above algorithm can be described by

$$\leq \leq$$ T(n)

$$\leq \left(\vphantom{\frac{n}{5}}\right. {\frac{n}{5}} \left.\vphantom{\frac{n}{5}}\right) \left(\vphantom{\frac{3n}{4}}\right. {\frac{3n}{4}} \left.\vphantom{\frac{3n}{4}}\right)$$

Let us guess the solution T(n) = Cn for n > 75. For n$\geq$ 75, assumeT(m) $\leq$Cm for m < n. Then

$$\leq \left(\vphantom{\frac{Cn}{5}}\right. {\frac{Cn}{5}} \left.\vphantom{\frac{Cn}{5}}\right) \left(\vphantom{\frac{3Cn}{4}}\right. {\frac{3Cn}{4}} \left.\vphantom{\frac{3Cn}{4}}\right)$$ T(n)

$$\leq {\textstyle\frac{19}{20}}$$

Thus T(n) is O(n).

• Instead of groups of 5, let us say we choose groups of 7. It is easy to show that the worst case complexity is again O(n). In general, any size of the groups that ensures the sum of the two arguments of T(.) to be less than nwill yield O(n) worst case complexity.