Radix sort using std::bitset

Hi all,

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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
double radixsort(int* toSort, uint size) {
	clock_t begin = clock();

        typedef unsigned int 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).
Last edited on
closed account (48bpfSEw)
Here is a code for radix sorting from wiki, if you like to compare your code with another one.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <map>
#include <vector>

template <typename ForwardIterator>
void radixsort(const ForwardIterator first, const ForwardIterator last, int factor = 10)
{
   // partitionieren
   std::map<int, std::vector<int> > buckets;
   for (ForwardIterator i = first; i != last; ++i) {
      // die gewünschte Ziffer ermitteln und im Bucket mappen
      if (factor == 10) buckets[*i%factor].push_back(*i);
      else buckets[(*i/(factor/10)) %10].push_back(*i);
   }

   // sammeln
   ForwardIterator copyfirst = first;
   for (int i = 0; i < 10; ++i) {
      for (std::vector<int>::const_iterator it = buckets[i].begin(); it != buckets[i].end(); )
         // Sammeln und Änderungen auf den Iteratorbereich [first, last) anwenden
         *copyfirst++ = *it++;
   }


   if (factor > *std::max_element(first, last)) {
      factor = 10;
      return;
   } else {
      factor *= 10;
      radixsort(first, last, factor);
   }
}


https://de.wikipedia.org/wiki/Radixsort

@edge6768

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.

Good Luck !!
In-place MSD radix sort (also from wiki)
https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
constexpr std::size_t NBITS = std::numeric_limits<unsigned int>::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
        const auto 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
        }
    }
}

http://coliru.stacked-crooked.com/a/be452a3ed750f50e
Topic archived. No new replies allowed.