Monday, August 26, 2013

Radix sorting code confusion

Radix sorting code confusion

I have a question about this algo:

(Slide taken from here.)
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 know after we accumulate counts they're supposed to be some sort of
offset. So we can insert the letters in proper place in temp[].
I'm just not sure what the a[i]++ is doing in there. (<-main question) I
know where referencing the letter in the count array, but why do we
increment the letter too? Did we change letters? Thanks.
Grateful for any help.

No comments:

Post a Comment