// 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;
}