The Standard Librarian: Sorting in the Standard Library

Listing 1: Measurements — sorting a vector<double>

#include <iostream>
#include <iomanip>
#include <fstream>
#include <utility>
#include <string>
#include <vector>
#include <list> 
#include <set>
#include <algorithm>
#include <assert.h>
#include <time.h>
#include <stdlib.h>

using std::pair;
using std::vector;
using std::string;

struct timer {
  clock_t start;

  timer() { start = clock(); }
  double time() const {
    return double(clock() - start) / CLOCKS_PER_SEC;
  }
};

template <class Container>
pair<string, double> 
do_sort(Container c)
{
  timer t;
  std::sort(c.begin(), c.end());
  return std::make_pair(string("sort"), t.time());
}

extern "C" int
dcompare(const void* px, const void* py)
{
  double x = *static_cast<const double*>(px);
  double y = *static_cast<const double*>(py);
  return x < y ? -1 : x > y ? 1 : 0;
}

pair<string, double>
do_qsort(vector<double> v)
{
  double* a = new double[v.size()];
  std::copy(v.begin(), v.end(), a);
  timer t;

  qsort(a, v.size(), sizeof(double), &dcompare);
  double elapsed = t.time();
  delete[] a;
  return std::make_pair(string("qsort"), elapsed);
}


template <class Container>
pair<string, double> 
do_stable_sort(Container c)
{
  timer t;
  std::stable_sort(c.begin(), c.end());
  return std::make_pair(string("stable_sort"), t.time());
}

template <class Container>
pair<string, double> 
do_heap_sort(Container c)
{
  timer t;
  std::make_heap(c.begin(), c.end());
  std::sort_heap(c.begin(), c.end());
  return std::make_pair(string("heap sort"), t.time());
}

template <class Container>
pair<string, double>
do_list_sort(Container c)
{
  typedef typename Container::value_type T;
  std::list<T> L(c.begin(), c.end());
  timer t;
  L.sort();
  return std::make_pair(string("list sort"), t.time());
}

template <class Container>
pair<string, double>
do_set_sort(Container c)
{
  typedef typename Container::value_type T;
  timer t;
  std::multiset<T> S(c.begin(), c.end());
  return std::make_pair(string("set sort"), t.time());
}

void report(vector<pair<string, double> > v,
            std::ostream& os)
{
  typedef vector<pair<string, double> > Vect;
  
  os << std::setw(20) << "sorting method" << "    " 
     << "t (sec)" << std::endl; 
  for (Vect::iterator i = v.begin(); i != v.end(); ++i)
    os << std::setw(20) << i->first << "    "
       << i->second << std::endl;
}

int main(int argc, const char**
argv)
{
  int N = 0;
  if (argc == 2)
    N = atoi(argv[1]);
  if (N <= 0) {
    std::cerr << "Usage: "
              << argv[0] << " <positive number>"
              << std::endl;
    return 1;
  }

  vector<double> v(N);
  for (int i = 0; i < N; ++i)
    v[i] = i;
  std::random_shuffle(v.begin(), v.end());

  std::cout << "Sorting a vector of "
            << v.size() << " doubles." << std::endl;
  vector<pair<string, double> > results;
  results.push_back(do_sort(v));
  results.push_back(do_qsort(v));
  results.push_back(do_stable_sort(v));
  results.push_back(do_heap_sort(v));
  results.push_back(do_list_sort(v));
  results.push_back(do_set_sort(v));

  report(results, std::cout);

  return 0;
}