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;

Please edit your question and provide a minimal reproducible example. — Jabberwocky
– Jabberwocky, Commented Oct 18, 2017 at 16:19
int C[k + 1]; is not legal C++. There are no VLAs. You may want to use std::vector instead. — n. m. could be an AI
– n. m. could be an AI, Commented Oct 18, 2017 at 16:30
Restricted from using vectors but not restricted from using non-standard non-portable constructs? You are taking an interesting class (from the entomological perspective). — n. m. could be an AI
– n. m. could be an AI, Commented Oct 18, 2017 at 19:42

user2736738 · Accepted Answer · 2017-10-18 18:21:57Z

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;

edited Oct 18, 2017 at 18:21

answered Oct 18, 2017 at 16:22

user2736738

31k5 gold badges45 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

zsloan112 Over a year ago

So i changed that section and still got the same output, however I did change the last for loop to for(int i = size; i >= 0; i++) and I got 0 0 0 1 2 2 3 3 4 5 which is close but it has an extra 0 at the beginning and not the 6 at the end.

user2736738 Over a year ago

@zsloan112.: i=size-1 You have iterated one extra time that's why geeting an extra 0. Make it frm i=size-1 and for(int i = size-1; i >= 0; i--)

zsloan112 Over a year ago

As soon as I changed it to i = size - 1 i got a segmentation fault

user2736738 Over a year ago

@zsloan112.: You should decrement i. Check for(int i = size-1; i >= 0; i--)

zsloan112 Over a year ago

That is what I have: for(int i = size - 1; i >= 0; i--)

|

Collectives™ on Stack Overflow

Not getting correct sorted array with a counting sort

1 Answer 1

Counting sort code:

main code

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Counting sort code:

main code

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related