c++-radix-sort

radix.cpp

#include <climits> // CHAR_BIT
#include <iostream>
#include <random>
#include <vector>
#include <chrono>

void lsd_radix_sort(std::vector<int> &in) {
  // get the size in bits of the ints
  unsigned int width = sizeof(int)*CHAR_BIT;
  // how much we'll shift over at each step
  unsigned int alphabet = 8;
  std::vector<int> counts (1 << alphabet);
  // the number of passes is the number of bits / bits-per-pass
  for (int pass = 0; pass < width / alphabet; pass++) {
    // perform counting sort
    // count up the number of elements in each bucket
    // in.at(i) >> d * pass  -> shift the value over to the bits we care about.
    // & ((1 << d))  -> remove all the bits ahead of the ones that we care about.
    for (int i = 0; i < in_len; i++)
      counts.at((in.at(i) >> alphabet * pass) & ((1 << alphabet)))++;
    // change the counts into array indexes
    for (int i = 1; i < (1 << alphabet); i++)
      counts.at(i) += counts.at(i - 1);
    // move through the input array and put the items in their buckets
    for (int i = in_len - 1; i >= 0; i--)
      in.at(--counts.at((in.at(i) >> alphabet * pass) & ((1 << alphabet) - 1))) = in.at(i);
  }
}

bool is_sorted(std::vector<int> in) {
  for (int i = 0; i < in.size() - 1; i++) {
    if (in[i] > in[i + 1])
      return false;
  }
  return true;
}

void fill_with_random(std::vector<int> in) {
  // get the max int size:
  int max_int = 0;
  // negate all the bits
  max_int = ~max_int;
  // shift over one to get rid of the negative
  max_int = (unsigned int)max_int >> 1;
  // @source: https://stackoverflow.com/a/19728404
  std::random_device rd;     // only used once to initialise (seed) engine
  std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
  std::uniform_int_distribution<int> uni(1, max_int); // guaranteed unbiased
  for (int i = 0; i < in.size(); i++) {
    in.at(i) = uni(rng);
  }
}

int main() {
  long in_len = 10000000000;
  static std::vector<int> test (in_len);
  fill_with_random(test, in_len);

  auto start = std::chrono::steady_clock::now();
  lsd_radix_sort(test, in_len);
  auto end = std::chrono::steady_clock::now();

  if (is_sorted(test, in_len)) {
    std::cout << "Sorted " << in_len << " integers in "
    << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
		<< " ms.\n";
  } else {
    std::cout << "sort failure" << std::endl;
  }
}