Smallest i numbers in sorted order. Given a set of n numbers, we wish to find th

Question

Smallest i numbers in sorted order. Given a set of n numbers, we wish to find the i smallest numbers in sorted order using a comparison-based algorithm. Analyze the running time of the following three methods in terms of n and i, and compare their efficiency. Be sure to comment on the expected running time and worst-case running time if they are different. Also, consider separately cases where i is much smaller than n and cases where i is close to n (i.e., i elementof Theta (n)). a. Sort the numbers and list the i smallest. b. Build a min-priority queue from the numbers, and call Extract-Min i times. c. Use the order-statistic algorithm (Rand-Select) to find the ith smallest number, partition around that number, and sort the i smallest numbers.

Explanation / Answer

(a) Sort the numbers, and list the i smallest
Solution:
Use any optimal sorting algorithm, such as MergeSort or HeapSort. Then this can be
done in (n lg n).
(b) Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.
Solution:
Call Build-Heap, (n). Then call Extract-Max, (lg i), i times. So, total running
time is (n + ilg i).
(c) Use an order-statistic algorithm to find the ith smallest number, partition around that
number, and sort the i smallest numbers.
Solution:
Select the i-th smallest number using SELECT, (n), call partition, (n), and then sort
the i smallest numbers, (ilg i). So our algorithm takes (n + ilg i).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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