I just wrote a simple iterative radix sort and I'm wondering if I have the right idea.
Recursive implementations seem to be much more common.
I am sorting 4-byte integers (unsigned to keep it simple).
I am using 1-byte as the 'digit'. So I have 2^8=256 buckets.
I am sorting the most significant digit (MSD) first.
After each sort I put them back into array in the order they exist in buckets and then perform the next sort.
So I end up doing 4 bucket sorts.
It seems to work for a small set of data. Since I am doing it MSD I'm guessing that's not stable and may fail with different data.
Did I miss anything major?
#include <iostream>
#include <vector>
#include <list>
using namespace std;
void radix(vector<unsigned>&);
void print(const vector<list<unsigned> >& listBuckets);
unsigned getMaxForBytes(unsigned bytes);
void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets);
int main()
{
unsigned d[] = {5,3,6,9,2,11,9, 65534, 4,10,17,13, 268435455, 4294967294,4294967293, 268435454,65537};
vector<unsigned> v(d,d+17);
radix(v);
return 0;
}
void radix(vector<unsigned>& data)
{
int bytes = 1; // How many bytes to compare at a time
unsigned numOfBuckets = getMaxForBytes(bytes) + 1;
cout << "Numbuckets" << numOfBuckets << endl;
int chunks = sizeof(unsigned) / bytes;
for(int i = chunks - 1; i >= 0; --i)
{
vector<list<unsigned> > buckets; // lazy, wasteful allocation
buckets.resize(numOfBuckets);
unsigned mask = getMaxForBytes(bytes);
unsigned shift = i * bytes * 8;
mask = mask << shift;
for(unsigned j = 0; j < data.size(); ++j)
{
unsigned bucket = data[j] & mask; // isolate bits of current chunk
bucket = bucket >> shift; // bring bits down to least significant
buckets[bucket].push_back(data[j]);
}
print(buckets);
merge(data,buckets);
}
}
unsigned getMaxForBytes(unsigned bytes)
{
unsigned max = 0;
for(unsigned i = 1; i <= bytes; ++i)
{
max = max << 8;
max |= 0xFF;
}
return max;
}
void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets)
{
int index = 0;
for(unsigned i = 0; i < listBuckets.size(); ++i)
{
list<unsigned>& list = listBuckets[i];
std::list<unsigned>::const_iterator it = list.begin();
for(; it != list.end(); ++it)
{
data[index] = *it;
++index;
}
}
}
void print(const vector<list<unsigned> >& listBuckets)
{
cout << "Printing listBuckets: " << endl;
for(unsigned i = 0; i < listBuckets.size(); ++i)
{
const list<unsigned>& list = listBuckets[i];
if(list.size() == 0) continue;
std::list<unsigned>::const_iterator it = list.begin(); // Why do I need std here!?
for(; it != list.end(); ++it)
{
cout << *it << ", ";
}
cout << endl;
}
}
Update:
Seems to work well in LSD form which it can be modified by changing the the chunk loop in radix as follows:
for(int i = chunks - 1; i >= 0; --i)