countingsort.cpp

// Counting sort
// 
// Simplified code as example for the counting sort algorithm.
//
// by feyd//godX.de
 
#include <vector>
#include <stdio.h>
 
// Base class, counting sort
template<class _TYPE>
class CCountingSort
{
public:
    CCountingSort() {}
    virtual ~CCountingSort() {}
 
    const std::vector<_TYPE>& Sort(const std::vector<_TYPE>& toSort, _TYPE nMin, _TYPE nMax)
    {
        // Clear counters
        std::vector<size_t> histogram(nMax-nMin+1);
        for(size_t n=0; n<histogram.size(); n++)
            histogram[n] = 0;
 
        // Count equal number parts
        for(size_t n=0; n<toSort.size(); n++)
        {
            _TYPE nValue = toSort[n];
            if(nValue<nMin)
            {
                printf("Value underflow\r\n");
                return m_empty;
            }
            if(nValue>nMax)
            {
                printf("Value overflow\r\n");
                return m_empty;
            }
            histogram[nValue-nMin]++;
        }
 
        // Build base positions
        size_t nBase = 0;
        for(size_t n=0; n<histogram.size(); n++)
        {
            size_t nCount = histogram[n];
            histogram[n] = nBase;
            nBase += nCount;
        }
 
        // Reorder
        m_output.resize(toSort.size());
        for(size_t n=0; n<toSort.size(); n++)
        {
            _TYPE nValue = toSort[n];
            m_output[histogram[nValue-nMin]] = nValue;
            histogram[nValue-nMin]++;
        }
 
        return m_output;
    }
 
    std::vector<_TYPE> m_output;
    std::vector<_TYPE> m_empty;
};
 
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
    printf("Counting sort test...\r\n\r\n");
 
    if(argc<3)
    {
        printf("Not enough arguments!\r\n");
        printf("Usage: countingsort <min> <max> values\r\n");
        return -1;
    }
    std::vector<int> arrayToSort;
    for(int n=3; n<argc; n++)
        arrayToSort.push_back(atoi(argv[n]));
 
    CCountingSort<int> sort;
    const std::vector<int>& output = sort.Sort(arrayToSort, atoi(argv[1]), atoi(argv[2]));
 
    printf("   sorted %d elements:\r\n", (int)output.size());
    for(size_t n=0; n<output.size(); n++)
        printf("      %d. %d\r\n", (int)n+1, output[n]);
    printf("\r\n");
    return 0;
}