Algorithms in C++

I am reading the book algorithms in C++ from Robert Sedgewick
Page 112 about Distribution Counting is this code

for (j = 0; j < M; j++) count[j] = 0;
for (i = 1; i <= N; i++) count[a[i]]++;
for (j = 1; j < M; j++) count[j] += count [j-1];
for (i = N; i >= 1; i--) b[count[a[i]]--] = a [i];
for (i = 1; i <= N; i++) a[i] = b[i];
I understand in general what this code do
What I wish someone could explain to me is count[a[i]]
this phrase and this b[count[a[i]]--] phrase.
Imagine M=4 and N=14
Just some explanation about when looking at count[a[i]]
is it count[A] or count [1] or when looking at b[count[a[i]]--]
how can I explain what is inside it.

*if thinking a[] is filled by "ABBACADABBADDA"
Would anyone please help
count[a[i]]
a[i] is being used as an index into count.
lets take a simple example:
int count [256] = {0};
string s = "XXX";
for(int i = 0; i < s.length(); i++)
count[s[i]]++; //s[i] is 'X' every time, this has an ascii value from 0-255 somewhere, as an integer. //so count['X'] is incremented. So we counted how many Xs we had in that string, which happens to be 3:
cout << count['X']; //verify

this is a twist on the 'counting sort' which is a specific case of a bucket sort. Instead of using it to sort the data, though, we just want the counting part.

if you ran it again on "XXXYYY" you would get count['X'] is 3 and count['Y'] is 3, and everything else is still zero. See it?
If you understand this, do you see how to use it as a sort? A double loop reproduces the data, and a single loop reproduces the sorted deduplicated data. Rough pseudocode for the double loop:

for(i = 0-255)
for(j = 0 to count[i])
cout (char)i //so if you had 3 'X's ... it would get to count['X'], loop 3 times, and spit out 'X' 3 times... sorted, because you go through count in sorted order.
Last edited on
Topic archived. No new replies allowed.