radixsort.cpp

// Radix sort
// 
// Simplified code as example for the radix sort algorithm.
//
// by feyd//godX.de
 
#include <vector>
#include <stdio.h>
 
// Base class, radix sort
template<class _TYPE, int _BITS>
class CRadixSort
{
public:
    CRadixSort() : m_histogram(1<<_BITS) {}
    virtual ~CRadixSort() {}
 
    const std::vector<_TYPE>& Sort(const std::vector<_TYPE>& toSort)
    {
        const std::vector<_TYPE>* pInput = &toSort;
        std::vector<_TYPE>* pOutput = &m_output1;
 
        int nRound = 0;
        for(int nBitPos=0; nBitPos<sizeof(_TYPE)*8; nBitPos+=_BITS)
        {
            // Clear counters
            for(size_t n=0; n<m_histogram.size(); n++)
                m_histogram[n] = 0;
 
            // Count equal number parts
            for(size_t n=0; n<pInput->size(); n++)
                m_histogram[((*pInput)[n]>>nBitPos)&((1<<_BITS)-1)]++;
 
            // Build base positions
            size_t nBase = 0;
            for(size_t n=0; n<m_histogram.size(); n++)
            {
                size_t nCount = m_histogram[n];
                m_histogram[n] = nBase;
                nBase += nCount;
            }
 
            // Reorder
            pOutput->resize(pInput->size());
            for(size_t n=0; n<pInput->size(); n++)
            {
                _TYPE nValue = (*pInput)[n];
                size_t nPos = (nValue>>nBitPos)&((1<<_BITS)-1);
                (*pOutput)[m_histogram[nPos]] = nValue;
                m_histogram[nPos]++;
            }
 
            // Swap buffers
            if(nRound&1)
            {
                pInput = &m_output2;
                pOutput = &m_output1;
            } else {
                pInput = &m_output1;
                pOutput = &m_output2;
            }
            nRound++;
        }   
        return *pInput;
    }
 
    std::vector<size_t> m_histogram;
    std::vector<_TYPE> m_output1;
    std::vector<_TYPE> m_output2;
};
 
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
    printf("Radix sort test...\r\n\r\n");
 
    std::vector<int> arrayToSort;
    for(int n=1; n<argc; n++)
        arrayToSort.push_back(atoi(argv[n]));
 
    CRadixSort<int, 8> sort;
    const std::vector<int>& output = sort.Sort(arrayToSort);
 
    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;
}