Counting Sort - Textbook is wrong?

[Arslan7041]

Im studying algorithms using the well-known Cormen, Leiserson, Rivest and Stein 3rd edition book.

On chapter 8, page 195, the book gives pseudocode for the counting sort algorithm. I studied the pseudocode, and understood it pretty well. But when I implemented it using C++, it would not work. Here is my implementation:

int main()
{
    int A[] = {2, 9, 5, 7, 8, 5, 10, 4};
    const int SIZE = sizeof(A)/sizeof(A[0]); // get SIZE of array
    int B[SIZE] = {};
    int k = *std::max_element(A, A + SIZE) + 1;

    countingSort(A, B, SIZE, k);
    for(int i : B) std::cout << i << " ";

    std::cout << "\n";
}

void countingSort(int A[], int B[], int SIZE, int k)
{
    int C[k];
    for(int i = 0; i < k; i++)
        C[i] = 0;

    for(int j = 0; j < SIZE; j++)
        C[A[j]]++;

    for(int i = 1; i < k ; i++)
        C[i] += C[i-1];

    for(int j = SIZE-1; j >= 0; j--)
        B[ C[A[j]]-- ] = A[j]; // post-decrement
    
}

When I looked it up online, I found a version where they use pre-decrement, so the last line looks like this:
B[ --C[A[j]] ] = A[j];. So I tried that and it works perfectly.

Is the textbook wrong?

(Note: The pseudocode in the texbook clearly decrements AFTER getting the element in C. I know this for sure because it has it as two separate statements)

[Peter87]

No the book is not wrong. The pseudocode assumes the indices for A and B start counting from 1. You seem to have taken this into account when implementing the function except on line 27. If C[A[j]] is 3 then B[C[A[j]]] is supposed to access the third element of B. To make this work as intended when the indices for B start from 0 instead of 1 you need to subtract one from the index.

B[C[A[j]] - 1] = A[j];
C[A[j]] = C[A[j]] - 1;

This is equivalent to the pre-decrement code that you found.

[Arslan7041]

Okay, good explanation, but...

The pseudocode assumes the indices for A and B start counting from 1

this is another thing im partially confused about. I know the book as a whole starts arrays from 1 (instead of 0), but the pseudocode for counting sort seems to conflict with this norm because:
(1) Array C is filled in starting at index 0
(2) When array C is being summed up in the third for-loop, it also seems that C starts with index 0, as the loop starts at 1 but adds the previous element (which must be element 0).

[Peter87]

It's explained in the paragraph that precedes the pseudocode.

In the code for counting sort, we assume that the input is an array A[1..n], and
thus A.length = n. We require two other arrays: the array B[1..n] holds the
sorted output, and the array C[0..k] provides temporary working storage.

When they write A[1..n] they mean that the indices for A goes from 1 to n,
and when they write C[0..k] they mean that the indices of C goes from 0 to k.
Note that n and k are part of the valid indices in the respective arrays.