Algorithms Problem: Largest i numbers in sorted order. Given a set of n numbers,

Question

Algorithms Problem:

Largest i numbers in sorted order. Given a set of n numbers, we wish to find the i largest numbers in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case run time, and analyze the run times of the algorithms in terms of n and i. Sort the numbers, and list the i largest. (Describe your algorithm and analyze its run time) Build a max-priority queue from the numbers, and call EXTRACT-MAX i times. Use an order statistic algorithm (e.g., SELECT) to find the ith largest number, partition around that number, and sort the i largest numbers. Which algorithm would you choose to solve the problem, and why?

Explanation / Answer

a) We use quicksort or mergesort algorithm to sort all the numbers in descending order.

Then we display the first i numbers in the sorted array.

The complexity of the above algorithm is O(nlgn + i).

O(nlgn) to sort the array and O(i) to display the first i numbers.

b) Building a max priority queue would take O(nlgn) time and then extract-max would take O(1) time and we would need to remove the top element which would take O(lgn) time.

Therefore the total complexity would be O(nlgn + i*lg(n))

c) Select algorithm would find the ith largest element in O(n). So we can get the i largest elements in O(n) time. Then sorting the i numbers would take O(ilg(i)) time.

Therefore total complexity would be O(n+i*lg(i))

Therefore it would be wise to choose algorithm in (c) as it solves the problem most efficiently and takes only O(n+i*lg(i)) time, whereas the other algorithms take time in the order of O(nlgn).

Also SELECT algorithm is much easier to implement and chances of making an error also reduce.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.