(Elements of programming interviews 11.8.)

Consider the problem of finding the `k`

th largest element in an unsorted array.
We can use the following modification of heap sort.

which runs in `O(N*log(K))`

time because each call to `heappush`

or `heappushpop`

is `O(log(K))`

.

In fact if we use a variation of quicksort we can get an *average-case* time complexity of `O(N)`

but a worst-case time complexity of `O(N^2)`

.
The idea is that by partitioning the array around a pivot element we can eliminate many elements of the array at once.
An extremely rough implementation might be as follows:

where the problem is that we have no way of guaranteeing that the randomly chosen element isnâ€™t the largest element each time.