How to use counting sort method implementation in C++

Question

I am now using a counting sort method to do the sorting, and for more detailed explanation about this method, please refer to counting_sort The codes are as follows:

    #include <iterator>
    #include <limits>

    template <typename iterator>
    void counting_sort(iterator const &begin, iterator const &end)
    {
        typedef std::iterator_traits<iterator>::value_type T;
        T max = std::numeric_limits<T>::max();
        T freq[max+1] = {0};
        iterator it;
        T c;

        for (it = begin; it < end; ++it) {
            freq[*it] += 1;
        }
        for (c = 0, it = begin; c < max; ++c)
            while (freq[c]-- > 0) {
                *it++ = c;
            }
        }
        while (freq[c]-- > 0) {
            *it++ = c;
        }
    }

I have difficult in using the codes to perform sorting. For example,

  int main(void)
    {
        const int NUM=20;
        unsigned char a[NUM];
        for(int i=0; i<NUM; i++)
            a[i] = i;
        a[0] = 100;
        a[3] = 15;
        std::vector<unsigned char> aArray(a,a+NUM);
        counting_sort(aArray.begin(),aArray.end());
        for(int i=0; i<aArray.size(); i++)
        {
            int value = aArray[i];
            std::cout<<value<<std::endl;
        }

        return 0;
    }

I always have compilation errors for T freq[max+1] = {0}, the error messages are as follows:

error C2057: expected constant expression
error C2466: cannot allocate an array of constant size 0

Any ideas on how to use the codes? Thanks.

You take the max of a type T max = std::numeric_limits<T>::max(); and add 1 on the next line, looks like an overflow to me. — Kiroxas
– Kiroxas, Commented Jun 20, 2014 at 8:56

borisbn · Accepted Answer · 2014-06-20 08:52:08Z

3

In C++ (instead od C) you can't declare an array with variable length. If max would be a constant, then you expression will be right. The decision is to declare a freq as a std::vector

std::vector< T > freq( (size_t)max + 1, 0 );

Another thing: max is a maximum number, that can be represented in T, that's why max+1 is illegal. You can try this:

T [ (size_t)std::numeric_limits<T>::max() + 1 ] = {0};

answered Jun 20, 2014 at 8:52

borisbn

5,07429 silver badges44 bronze badges

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

Collectives™ on Stack Overflow

How to use counting sort method implementation in C++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related