Not getting correct sorted array with a counting sort

Question

I am working on the Counting Sort Algorithm currently. I have set up two temporary arrays C and B. C is to count the number of times a number in the original array appears. It then uses the elements in C to place the elements in A (original array) into the correct location in B. I have my countingSort function print out C after each loop to ensure that it has the correct values in it (which it does, I'm testing it with a small sample size). The problem occurs when I go to insert the elements of A into B with the help of C.

Here is my function for countingSort:

Note: I pass an array of 10 integers 2 0 3 2 5 4 3 6 10 to the function,the temporary array B, the maximum value (so I know what size to make C) and the size of array A

void countingSort(int A[], int B[], int k, int size){
    int C[k + 1];
    cout << "K: " << k << endl;

    for(int i = 0; i < k + 1; i++){
        C[i] = 0;
    }



    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }


    for(int i = 0; i < size; i++){
        C[A[i]] = C[A[i]] + 1;
    }

    cout << endl;


    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }


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


    cout << endl;
    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }



    for(int i = size + 1; i > 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }


    cout << endl;
    for(int i = 0; i < size; i++){
        cout << B[i] << " ";
    }


}

As you can see I print out C after each loop, so after the first loop it should show that C is 0 0 0 0 0 0, which it does print out correctly. After the next for loop it C should be 2 1 2 2 1 1 1, which it also prints out correctly. Next it adds the elements of C up to get 2 3 5 7 8 9 10, which is also printed out correctly. Now my issue arises here when I try to put the elements of A into B. It is supposed to print 0 0 1 2 2 3 3 4 5 6, but it prints 0 0 0 1 0 2 3 3 4 5 instead.

I have tried playing around with my indexes on the last for loop, but just cant seem to figure out what is causing B to be incorrect. How could I fix this issue? My overall goal is to get the count sort to work for a randomly generated array of size 40 with numbers between 1 and 25.

Edit: Main Function where I call countingSort:

int sizeCount1 = 10;
int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0};

cout << "Counting Sort Version 1 (Pre Sort)" << endl;

for(int i = 0; i < sizeCount1; i++){
    cout << countOne[i] << " ";
}

cout << endl;


for(int i = 0; i < sizeCount1; i++){
    countTemp[i] = 0;
}



int max = 0;
for(int i = 0; i < sizeCount1; i++){
    if(countOne[i] > max){
        max = countOne[i];
    }
}

cout << "Max: " << max << endl;


countingSort(countOne, countTemp, max, sizeCount1);

cout << endl;

cout << "Counting Sort Version 1 (Post Sort)" << endl;


for(int i = 1; i < 10; i++){
    cout << countTemp[i] << " ";
}

cout << endl << endl;

Answer 1

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

Otherwise you are getting undefined behavior.

Also in the output array formation

for(int i = size-1; i >= 0; i--){
    B[C[A[i]]] = A[i];
    C[A[i]] = C[A[i]] - 1;
}

You got the algorithm right. Now just dry run a bit. That way you can find these kind of errors in your code.

_{As the OP used the 0-indexing. I am using the same in my answer}

_{In case you can't use vector ..allocate memory using new. Check the reference a bit for this.}

_{Another thing is whenever you code counting sort always try to prove that you can hold the range in the auxiliary arrays. That helps.}

Counting sort code:

void countingSort(int A[], int B[], int k, int size){
    int C[k + 1];
    for(int i = 0; i < k + 1; i++){
        C[i] = 0;
    }
    for(int i = 0; i < size; i++){
        C[A[i]] = C[A[i]] + 1;
    }
    for(int i = 0; i < k + 1; i++){
        C[i] = C[i] + C[i - 1];
    }
    for(int i = size-1; i >= 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }
}

main code

int sizeCount1 = 10;
int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0};

cout << "Counting Sort Version 1 (Pre Sort)" << endl;

for(int i = 0; i < sizeCount1; i++){
    countTemp[i] = 0;
}
int max = 0;
for(int i = 0; i < sizeCount1; i++){
    if(countOne[i] > max){
        max = countOne[i];
    }
}

cout << "Max: " << max << endl;


countingSort(countOne, countTemp, max, sizeCount1);
cout << "Counting Sort Version 1 (Post Sort)" << endl;
for(int i = 0; i < 10; i++){
    cout << countTemp[i] << " ";
}

cout << endl << endl;