9.7.2 Algorithm 2

Variation of quicksort.

    Select (i, j, k) /* finds the k^th element among A[i]  ^...  A[j]  */
{

            pick a pivot element v;

            partition A[i]  ^...  A[j] so as to get

A[i]  ^...  A[m - 1] with keys < v and

A[m]  ^...  A[j] with keys $\geq$v;

            if(k$\leq$m - 1)

                Select (i, m - 1, k)

           else

                Select (m, j, k - m + i)

}

• Worst case complexity of the above algorithm is O(n²) (as in quicksort).
• Average Case:
• Note that select calls itself only once at a time whereas quicksort called itself twice each time.
• On an average, select calls itself on a subarray half as long as the subarray. To be conservative, suppose that each call of select is on an array $\left(\vphantom{\frac{9}{10}}\right.$${\frac{9}{10}}$$\left.\vphantom{\frac{9}{10}}\right)^{\rm th}_{}$ the size on previous call. Then, 
T(n) $$\leq$$Cn + T$$\left(\vphantom{\frac{9n}{10}}\right.$$$${\frac{9n}{10}}$$$$\left.\vphantom{\frac{9n}{10}}\right)$$ which can be shown to be O(n).