bogosort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <random>
#include <chrono>

static void usage(const char *progname)
{
  std::cerr << "Bogosort : A program implementing the bogosort algorithm.\n";
  std::cerr << "Usage : " << progname << " <num of elements>\n";
  std::cerr << "The sorted data consists of pseudorandom unsigned integers.\n";
  std::cerr << "The program prints the total time taken to sort the input "
    "to stdout." << std::endl;
}

template<typename T, class URNG>
static void bogosort(std::vector<T> &vec, URNG &&g)
{
  while(!std::is_sorted(vec.begin(), vec.end()))
    std::shuffle(vec.begin(), vec.end(), g);
}

static void run_test(std::size_t numElems)
{
  // the timer stuff can be very long to write, let's import these locally.
  using std::chrono::high_resolution_clock;
  using std::chrono::duration_cast;
  using std::chrono::milliseconds;
  using std::chrono::time_point;
  
  // initialize the random stuff : a device for seeding the engine, and a
  // uniform distribution for actually generating integers based on the
  // engine's output.
  std::random_device rndDev;
  std::default_random_engine rndEngine(rndDev());
  std::uniform_int_distribution<int> rndDistrib;
  
  // now, actually generate the data that's about to be sorted. TODO : use
  // decltype (dependent on the distribution's template parameter) for the
  // vector's template parameter.
  std::vector<int> dataToSort(numElems);
  std::generate(dataToSort.begin(), dataToSort.end(), 
    [&]{ return rndDistrib(rndEngine); });
  
  // call the function and measure the time it has taken to execute.
  auto beforeBogo = high_resolution_clock::now();
  bogosort(dataToSort, rndEngine);
  auto afterBogo = high_resolution_clock::now();
  
  // print the result.
  std::cout << "The function took " << 
    duration_cast<milliseconds>(afterBogo - beforeBogo).count() <<
    " ms to execute." << std::endl;
}

int main(int argc, char **argv)
{
  try
  {
    if(argc != 2)
      throw std::invalid_argument("The program accepts two arguments");
    
    int numElems { std::stoi(argv[1]) };
    if(numElems < 0)
    {
      throw std::invalid_argument("The number of elements can't be "
        "negative");
    }
    run_test(numElems);
  }
  // invalid_argument or out_of_range might be thrown by std::stoi().
  catch(const std::logic_error &e)
  {
    std::cerr << "Error : " << e.what() << std::endl;
    usage(argv[0]);
    return 1;
  }
  return 0;
}