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

typedef std::vector<int> Array;

typedef std::chrono::high_resolution_clock Clock;
typedef Clock::rep TimeCount;
typedef Clock::time_point TimePoint;
typedef Clock::duration TimeDuration;

template<typename Func>
TimeCount getElapsedTime(Func f) {
    TimePoint start = Clock::now();
    f();
    TimePoint end = Clock::now();
    TimeDuration elapsed = end - start;
    return elapsed.count();
}

template<typename Arr>
void shuffleArray(Arr &chng) {
    static std::random_device rng;
    static std::mt19937 urng(rng());
    std::shuffle(std::begin(chng), std::end(chng), urng);
}

template<typename Arr>
void printArray(const Arr &in) {
    size_t i = 1;
    std::cout << "{ ";
    for (auto a: in) {
        if (i > 1) {
            std::cout << ", ";
        }
        std::cout << a;
        ++i;
    }
    std::cout << " }" << std::endl;
}

int main() {
    const int N = 20;
    //Array arr(N);
    int arr[N];
    for (int i = 1; i <= N; ++i) {
        arr[i - 1] = i;
    }

    std::random_device rng;
    std::mt19937 urng(rng());

    shuffleArray(arr);

    printArray(arr);

    TimeCount elapsed = getElapsedTime([&]{
        std::sort(std::begin(arr), std::end(arr));
    });
    printArray(arr);
    std::cout << elapsed << std::endl;

    const int R = 1000000;
    long long s = 0;
    for (int i = 0; i < R; ++i) {
        shuffleArray(arr);
        elapsed = getElapsedTime([&]{
            std::sort(std::begin(arr), std::end(arr));
        });
        s += elapsed;
    }
    s /= R;
    std::cout << "Average time: " << s << std::endl;
}