test_sort.cpp

#include <vector>
#include <algorithm>
#include <iterator>
#include <chrono>
#include <random>
#include <iostream>
#include <functional>

std::vector<int> all_equal(std::vector<int>::size_type n) {
    return std::vector<int>(n, 1000000);
}

std::vector<int> sorted(std::vector<int>::size_type n) {
    std::vector<int> v(n);
    std::iota(begin(v),end(v), 1);
    return v;
}

std::vector<int> reverse(std::vector<int>::size_type n) {
    std::vector<int> v = sorted(n);
    std::reverse(begin(v),end(v));
    return v;
}

std::vector<int> even_odd(std::vector<int>::size_type n) {
    std::vector<int> v(n);
    int i = -2;
    std::generate(begin(v), begin(v) + v.size()/2, [&] { i+=2; return i; });
    i = -1;
    std::generate(begin(v) + v.size()/2, end(v), [&] { i+=2; return i; });
    return v;
}

std::vector<int> reverse_even_odd(std::vector<int>::size_type n) {
    std::vector<int> v = even_odd(n);
    std::reverse(begin(v),end(v));
    return v;
}

std::vector<int> pipe_organ(std::vector<int>::size_type n) {
    std::vector<int> v = even_odd(n);
    std::reverse(begin(v) + v.size()/2,end(v));
    return v;
}

std::vector<int> push_front(std::vector<int>::size_type n) {
    std::vector<int> v = sorted(n);
    v.back() = v.front() - 1;
    return v;
}
std::vector<int> push_middle(std::vector<int>::size_type n) {
    std::vector<int> v = sorted(n);
    v.back() = v.front() - 1;
    return v;
}

std::vector<int> random(std::vector<int>::size_type n) {
  std::mt19937 eng;
  std::uniform_int_distribution<int> dist;
  std::vector<int> v(n);
  std::generate(begin(v), end(v), std::bind(dist,eng));
  return v;
}

void time(char const *label, std::vector<int> &v) {
  auto start = std::chrono::steady_clock::now();
  std::sort(begin(v), end(v));  
  auto end = std::chrono::steady_clock::now();
  std::cout << label << ": " << (end-start)/std::chrono::microseconds(1) << "us\n";
}

void test(char const *label, std::vector<int> v) {
    time(label, v);
}

int main() {
    #define TEST(X) test(#X, X(1000000))
    TEST(all_equal);
    TEST(sorted);
    TEST(reverse);
    TEST(even_odd);
    TEST(reverse_even_odd);
    TEST(pipe_organ);
    TEST(push_front);
    TEST(push_middle);
    TEST(random);
}