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 y开发者_StackOverflow中文版ou 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];

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.

There are 101 grades, 0 - 100

int count[101]; /*init to 0’s */

Fill count[] with the totals for each grade, e.g. count[90]=4 means four people got a 90%

for (i = 0; i < n; i++) count[S[i].grade]++;

Next, convert those totals to a running tally, i.e. if 57 people got lower than a 90, then count[90] = 57 + 4, or 61. So for each count[n], you have the number of people who got that grade or lower. This is important for the final array... you need 61 elements in the final array to hold everyone who got a 90 or lower. Note that count[100] should = n passed in.

count[0]-- is shifting the entire counts down by one, which converts a 1-based final array to a 0-based final array, e.g. if I have one person who got a zero, count[0] = 1, so my final array would start at NS[1]. I want to start at NS[0]. So the 61 elements above are now 60

count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];

Finally (wish he'd stop reusing 'i'), find the place for each grade... if there are 60 people with '90' or below, grade '90' belongs in the 60th element of the final array, NS. This is confusing, in part, because of the '--'... remember, there are 60 for grade '90', so the first '90' you come to will be placed at NS[60], because there are 59 people with lower grades. The count for '90' is decremented to 59, so the next '90' will be placed at NS[59]. And so forth.

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

The end result is a lowest-grade to highest-grade array, with NS[0] being the lowest grade, and NS[n] being the highest.

Make sense? It's really a beautiful algorithm!