Professor Dumbledore (a long lost brother of the beloved headmaster) teaches alg

Question

Professor Dumbledore (a long lost brother of the beloved headmaster) teaches algorithms in Magicland. After the first midterm exam, he wants to carefully scrutinize the students' performance, but unfortunately, the TAs handed him an unsorted array of scores L = x_1, , ..., x_n and left on vacation in Spring Break. Having come to know of your prowess in algorithms after taking COMPSCI 330, he recruits you to come up with an algorithm to sort these scores. If there were only k distinct scores among all n scores, can you sort L in O(n log k) time? Note that this does not necessarily imply that the set of possible scores is {1, k}. Also note that k is much smaller than n; therefore, an O(n log n) time algorithm will not suffice. (An O{n log k + k_2) solution will get partial credit.)

Explanation / Answer

Counting sort will be the best suitable slgo. for this purpose as count sort algorithm doesn't based on comparisons and supports duplication. It will run in O(n+k). Counting sort can be given as:

a.) find the min and max from the given numbers; and define the range.

b.) count the occurence of frequency of each element in a separate array say count[]

c.) now, modify the values of count array to store cumulative frequencies of given elements in it.

d.) now using the above modified array count, it places the values in the correct order.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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