Radix sort question

I have a question about this algo:

http://i.imgur.com/aax89z7.png

1
2
3
4
5
6
7
8
9
10
int N = a.length;
int[] count = new int[R];
for (int i = 0; i < N; i++)
 count[a[i]+1]++;
for (int k = 1; k < 256; k++)
 count[k] += count[k-1];
for (int i = 0; i < N; i++)
 temp[count[a[i]++]] = a[i]
for (int i = 0; i < N; i++)
 a[i] = temp[i];


Can someone elaborate about the 3rd for loop where we move the records from a[] to temp[]?

I'm just not sure how its getting done, especially confusing me with the a[i]++ in there.

Grateful for any help.
Looks like a typo. Should be
temp[count[a[i]]++]

Just FYI, the original line could mean different things for different C++ compilers.
Which original line?

If I break this up, it looks like this right?

1
2
3
4
char c = a[i];
int x = count[c];
temp[x] = c;
count[c]++;

Does that look right? Or does it increment before temp uses the value?
Last edited on
Also, since we made counts[a[i]+1]++ on the first for loop, we increment the type_i+1's frequency right?

On the slide it should be a=0, b=2, c=5... right?
This line: temp[count[a[i]++]] = a[i]

Your code is correct, but IMO it's more difficult to follow than the original, because of all the assignments.
Thanks a lot, helios.
Topic archived. No new replies allowed.