algorithm - Find the k largest elements in order

Question

What is the fastest way to find the k largest elements in an array in order (i.e. starting from the largest element to the kth largest element)?

Answer 1

One option would be the following:

1. Using a linear-time selection algorithm like median-of-medians or introsort, find the kth largest element and rearrange the elements so that all elements from the kth element forward are greater than the kth element.

2. Sort all elements from the kth forward using a fast sorting algorithm like heapsort or quicksort.

Step (1) takes time O(n), and step (2) takes time O(k log k). Overall, the algorithm runs in time O(n + k log k), which is very, very fast.

Hope this helps!