9-1 Largest $i$ numbers in sorted order

Given a set of $n$ numbers, we wish to find the $i$ largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of $n$ and $i$ .

a. Sort the numbers, and list the $i$ largest.

b. Build a max-priority queue from the numbers, and call $\text{EXTRACT-MAX}$ $i$ times.

c. Use an order-statistic algorithm to find the $i$th largest number, partition around that number, and sort the $i$ largest numbers.

a. The running time of sorting the numbers is $O(n\lg n)$, and the running time of listing the $i$ largest is $O(i)$. Therefore, the total running time is $O(n\lg n + i)$.

b. The running time of building a max-priority queue (using a heap) from the numbers is $O(n)$, and the running time of each call $\text{EXTRACT-MAX}$ is $O(\lg n)$. Therefore, the total running time is $O(n + i\lg n)$.

c. The running time of finding and partitioning around the $i$th largest number is $O(n)$, and the running time of sorting the $i$ largest numbers is $O(i\lg i)$. Therefore, the total running time is $O(n + i\lg i)$.