Radix sort – another language comparison exercise

I was reading the Wikipedia page for Radix sort[1] and I noticed a pretty terrible example for C++, so I set about writing my own, which I’ve included in the wiki as a modernized C++14 version.

#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <random>

int main()
{
  using INT = std::mt19937_64::result_type;
  std::array<INT, 200000> randoms;
  std::generate(randoms.begin(), randoms.end(), [engine = std::mt19937_64{}]() mutable {return engine();});
  std::array<std::vector<INT>, 256> buckets;

  for (auto r : randoms) std::cout << r << std::endl;
  std::cout << std::endl;

  for (int i = 0; i < sizeof(INT); ++i)
  {
    for (auto r : randoms) buckets[(r >> (i << 3)) & 0xFF].push_back(r);

    auto j = randoms.begin();
    for (auto& bucket : buckets)
    {
      for (auto b : bucket) *(j++) = b;
      bucket.clear();
    }
  }

  for (auto r : randoms) std::cout << r << std::endl;

  return 0;
}

1: http://en.wikipedia.org/wiki/Radix_sort

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s