Skip to content

Latest commit

 

History

History
executable file
·
125 lines (87 loc) · 3.43 KB

radix-sort.md

File metadata and controls

executable file
·
125 lines (87 loc) · 3.43 KB

Radix Sort

Discussion

This is an implementation of the radix sort algorithm that uses base 256.

Source Code

This uses base 256 to do the radix sort

#include <iostream>
#include <vector>
#include <deque>
#include <iterator>
#include <algorithm>
using namespace std;

// We can speed it up by switching to base 256. 256 = 0xff or one byte. We divide by
// 256 by shifting 8 bits to the right. 

void radix_sort_base256(vector<unsigned int> & x)
{
  if ( x.empty() ) {

          return; // need at least one element
  }

  typedef vector<unsigned int> input_type;

  // buckets_type is a deque of deques of unsigned ints.
  typedef deque< deque < input_type::value_type > > buckets_type;

  
  buckets_type buckets(256); // allocate buckets for sorting by base 256 numbers
                             // each element is a deque of unsigned int.

  // find maximum in the array to limit the main loop below
  input_type::value_type max = *max_element(x.begin(), x.end()); 

  // We sort while we still have base256 "columns" to examine. 

  // Note: Instead of using the division operator below, for example
  //
  //    for(; max != 0 ; max /= 256, pow256 *= 256) {
  //
  // we instead simply shift right to multiply by powers of 256.
  for(auto bits_2shift = 0; max != 0 ; max >>= 8, bits_2shift += 8)   {

      // 1. determine which bucket each element in x should enter
      for(input_type::const_iterator elem = x.begin(); elem != x.end(); ++elem) {

              // Use current rightmost digit to determine bucket number
              // We shift right to multiply by successive powers of 256, then do
              // bitwise AND to get the last base256 digit.  This process is faster
              // than doing:
              //
              // int const bucket_num = ( *elem / pow256 ) % 256;
              int const bucket_num = ( *elem >> bits_2shift) & 0xff; 

              // add the element to the list in the bucket:
              buckets[ bucket_num ].push_back( *elem );
      }

      // 2. transfer results of buckets back into the main input array.
      input_type::iterator store_pos = x.begin();

      // for each bucket:
      for(buckets_type::iterator bucket = buckets.begin(); bucket != buckets.end(); ++bucket) {

              // for each element in the bucket:
              for(buckets_type::value_type::const_iterator bucket_elem = bucket->begin();
                      bucket_elem != bucket->end(); ++bucket_elem)  {

                      // copy the element into next position in the main array
                      *store_pos++ = *bucket_elem;
              }

              bucket->clear(); // forget the current bucket's list of numbers
      }
  }
}

Main test program

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
#include "radix256.h"

using namespace std;

int RandomNumber ()
{
        return (rand() % 1000);
}

int main(int argc, char** argv) 
{
    vector<unsigned> input(20);

    generate (input.begin(), input.end(), RandomNumber);

    // using built-in random generator:
    random_shuffle ( input.begin(), input.end() );

    cout << " ** Elements before sorting: " << endl;

    copy(input.begin(), input.end(), ostream_iterator<unsigned int>(cout, " "));

    radix_sort_base256(input);

    cout << endl << " ** Elements after sorting: " << endl;

    copy(input.begin(), input.end(), ostream_iterator<unsigned int>(cout, " "));

    cout << endl;

    return 0;

}