I'm on summer break and thought I would give myself a project to keep me busy and learning during my offtime. Last semester my class covered sorting and radix sort was mentioned but not covered, so I thought this would be a good thing to cover myself. I also wanted to use the std::bitset as it's the only std container I have yet to use and thought it could be useful (?) for a radix sort.
Here is the function I have for the radix sort so far:
double radixsort(int* toSort, uint size) {
clock_t begin = clock();
typedefunsignedint uint;
const uint bitsetSize = (sizeof(int) * CHAR_BIT);
bitset<bitsetSize>* bitsToSort = nullptr;
try {
bitsToSort = new bitset<bitsetSize>[size];
}
catch (std::bad_alloc& ba) {
cerr << "Memory allocation error: " << ba.what() << '\n';
exit(1);
}
// Copy toSort into bitsToSort
for(uint i = 0; i < size; i++) {
bitsToSort[i] = toSort[i];
}
for(int i = 0; i < bitsetSize; i++) { // Loop bits
for (uint left = 0, right = size - 1; left < right; ) { // Loop elements
if( (bitsToSort[left])[i] == 1 ) { // CASE: Bit is a 1
std::swap(bitsToSort[left], bitsToSort[right--]);
}
else { // CASE: Bit is a 0
std::swap(bitsToSort[right - 1], bitsToSort[left++]);
} // END if/else
} // END for(left, right)
} // END for(i)
clock_t end = clock();
// Debug sterfs
for(uint i = 0; i < size; i++) {
toSort[i] = bitsToSort[i].to_ulong();
cout << toSort[i] << " " << bitsToSort[i] << '\n';
}
delete[] bitsToSort;
bitsToSort = nullptr;
return diffClocks(begin, end);
}
It seems to sort bits and pieces of the array but not all of it. I used unsigned integers to try and avoid any weirdness with sign bits and whatnot as that stuff is still over my head.
I guess my question is if this is a problem with my algorithm (generic radix) or if this is a problem with applying a generic radix sort to bits of an unsigned integer (or, more than likely, both).
Just thought I would mention, there is no need to use the new operator, it's bad news all round and the STL containers already put their data on the heap. If one use the STL containers, there is no need to worry about memory management.
One of the main problems with it is in the case where something throws an exception, the delete is never reached.
Also there is no need to use raw pointers anywhere.
constexpr std::size_t NBITS = std::numeric_limits<unsignedint>::digits ;
using bits = std::bitset<NBITS> ;
// in-place most significant bit radix sort (aka binary quicksort)
void sort( std::vector<bits>::iterator begin, std::vector<bits>::iterator end, std::size_t bitpos ) // bitpos zero is lsb
{
if( begin != end )
{
// partition into two bins based on bit at bitpos
constauto end_of_zeroes_bin = std::partition( begin, end, [bitpos]( bits v ) { return !v[bitpos] ; } ) ;
if( bitpos > 0 )
{
sort( begin, end_of_zeroes_bin, bitpos-1 ) ; // sort the zeroes bin on the next bit position
sort( end_of_zeroes_bin, end, bitpos-1 ) ; // sort the ones bin on the next bit position
}
}
}