Q:

How to sort an array of student records by their grade

Hey all, im studying for an exam at the moment, and I can't seem to understand this concept.
The question is, if your given an array of student records, where the members of the record are the student name and their grade, how can you sort it by grade. The professor gave this example of what he called a 'Distributed Counting Sort'. I'm having trouble understanding it, and was hoping someone could give me the pseudocode or algorithm for the code below,
Thanks :)
Function Distribution_counting_sort(S, n){
//Input: a student array S of n records
//Output: a sorted array (wrt grade) NS
int count[101]; /*init to 0’s */
/* counting */
for (i = 0; i < n; i++) count[S[i].grade]++;
/* accumulating */
count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];
/* distribution */
for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

A:

This is essentially a variation of Bucket Sort.
These are the buckets, one for each possible grade:
int count[101]; /*init to 0’s */

This counts how many students have each grade. This tells us the size of each bucket:
for (i = 0; i < n; i++) count[S[i].grade]++;

This converts the counts to be cumulative. This gives us the ending position of each bucket in the destination array. The count[0]-- bit is to account for 0 based arrays, I believe.
count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];

Now it places each student at the end of his/her bucket, and decrements the position value for that bucket.
for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

The nice thing about this kind of sort is that it's O(n), rather than O(n*log(n)). It only works for things that can be discretized into a finite (and manageable) number of buckets, however.
One thing that's a bit funny about this code is that it reverses the ordering of students that have the same grade. You could probably modify it to be a stable sort by changing the cumulative counts to be bucket starting positions and incrementing them when populating NS, or even easier, walk through S backwards in that last loop.

