Describe and analyze an algorithm that takes an unsorted array A of n integers (

Question

Describe and analyze an algorithm that takes an unsorted array A of n integers (in an unbounded range) and an integer k, and divides A into k equal-sized groups, such that the integers in the first group are lower than the integers in the second group, and the integers in the second group are lower than the integers in the third group, and so on. For instance if A = {4, 12, 3,8, 7,9, 10, 20,5) and k 3, one possible solution would be Aq = {4, 3, 5},Ag = {8.7,9), A3 = {12, 10, 20). Sorting A in 0(n log n)-time would solve the problem, but we want a faster solution. The running time of your solution should be bounded by O(nk). For simplicity, you can assume that is n a multiple of k, and that all the elements are distict. Note: k is an input to the algorithm, not a fixed constant.

Explanation / Answer

Solution:

Algorithm:

The algorithm using min heap is defined below:

Time complexity: O(k + (n-k)Logk) without sorted output for extracting each K elements of given array

so final time complexity will be O(k + (n-k)Logk) * ((n-k)/k) which is almost equivalent to O(nk).

I hope this helps, please let me know in case of any doubt. Thumbs up if this helped.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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