CODEWITHSUNDEEP
c++sortingcounting-sort
Dumbo
Dumbo

Reputation: 51

Counting Sort in C++

I am trying to implement the Counting Sort in C++ without creating a function. This is the code that I've written so far, but the program doesn't return me any values. It doesn't give me any errors either. Therefore, what is wrong?

#include <iostream>

using namespace std;

int main()
{
    int A[100], B[100], C[100], i, j, k = 0, n;

    cin >> n;

    for (i = 0; i < n; ++i)
    {
        cin >> A[i];
    }

    for (i = 0; i < n; ++i)
    {
        if (A[i] > k)
        {
            k = A[i];
        }
    }

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

    for (j = 0; j < n; ++j)
    {
        C[A[j]]++;
    }

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

    for (j = n; j > 0; --j)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] -= 1;
    }

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

    return 0;
}

Upvotes: 0

Views: 428

Answers (1)

scohe001
scohe001

Reputation: 15446

It looks like you're on the right track. You take input into A, find the largest value you'll be dealing with and then make sure you zero out that many values in your C array. But that's when things start to go wrong. You then do:

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

for (j = n; j > 0; --j)
{
    B[C[A[j]]] = A[j];
    C[A[j]] -= 1;
}

That first loop will always go out of bounds on the first iteration (C[i-1] when i=0 will be undefined behavior), but even if it didn't I'm not sure what you have in mind here. Or in the loop after that for that matter.

Instead, if I were you, I'd create an indx variable to keep track of which index I'm next going to insert a number to (how many numbers I've inserted so far), and then I'd loop over C and for each value in C, I'd loop that many times and insert that many values of that index. My explanation may sound a little wordy, but that'd look like:

int indx = 0;
for(int x = 0; x <= k; x++) {
    for(int y = 0; y < C[x]; y++) {
        B[indx++] = x;
    }
}

If you replace the two loops above with this one, then everything should work as expected.

See a live example here: ideone

Upvotes: 3

Related Questions