Algorithms: Divide and Conquer (Application of Quick Sort?!)

Question

Any help regarding how the problem below can be approached will be appreciated. I have also posted some thoughts on the problem.

You are the TA for a class with an enrollment of n students. You have their final scores (unsorted), and you must assign them one of the G available grades (A, B, C etc.). The constraints are (assuming n is a multiple of G):

• Exactly (n/G) students get each grade (for example, if n = 30, and G = {A,B,C}, then exactly 10 students get A, 10 get B, and 10 get C)
• A student with lower score doesn’t get a higher grade than a student with a higher score (however, they may get the same grade) Assuming that each student received a different score, derive an efficient algorithm and give its complexity in terms of n and G. Any algorithm that first sorts the scores will receive zero credit.

My answer: Okay, the last line of the problem says I am no good if I try to sort the array first and divide the array into G equal parts. This would take O(n log n) when the best sorting algorithm is used. So, I thought about an intricate solution. I see this problem as an instance where quick sort can come handy, since we don't need the students belonging to the same grade to be sorted, We can have k pivotal elements and the pivotal elements are all equally spaced. But, we are not given the marks of students and we are also told that each student has distinct scores.

First off, I compute the maximum and minimum score using the MaxMin Divide and Conquer Algorithm which would take O(n) time. Using the Maximum and Minimum we can roughly find the pivotal elements for each grade by calculating. (Max-Min)/k = lowest grade, 2*(Max-Min)/k = 2nd lowest grade. and k-1*(Max-Min)/k = highest grade.

Now using these as the pivotal elements we can perform only the partition method for quick sort which take n amount of time for the first time, n-(Max-Min)/k the second time and so on. So the time complexity of the algorithm would be O(n) since the min-max problem has the complexity O(n) and the Partition in Quick sort has the complexity of O(n).

Please share your thoughts.

Answer 1

You can put all the scores in a (max) priority queue then extract groups of n/G from it. This is still an implicit sorting but nonetheless is not prohibited from the rules.

Answer 2

This is basically a selection problem, only that you do G selections at once.

A modification of http://en.wikipedia.org/wiki/Quickselect algorithm should work here. While Quicksort always recursively descends into both partitions and original Quickselect only descends into the one that contains the kth index, the algorithm for this problem should descend into a partition if and only if it contains one of the n/G, 2*n/G, ... (G-1)*n/G array indexes - the ones that are splitting points between grades.

These indexes are the splitting points between grades, so you end up with an array where elements between the splitting points are not necessarily sorted, but the blocks between the points are.