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