Problem 6 - Selection Algorithm

Suppose $n$ integers are stored in an array $a$ from $a[1]$ to $a[n]$. Give an efficient algorithm which finds the $k$th largest element among them. Evaluate the average-case complexity of the algorithm in terms of $n$ and $k$.

See [SED00] for a detailed answer.