(Elements of programming interviews 11.8.)
Consider the problem of finding the
kth 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
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
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.