sort_benchmarks.cpp

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


// NOTE: All iterator concepts are experimental. I'm not going
// to concentrate on them
// See: http://en.cppreference.com/w/cpp/concept

using data_type = int;

// -- Helper I/O functions

template <typename ForwardIterator>
void print_container(ForwardIterator begin_it, ForwardIterator end_it)
{
    while (begin_it != end_it)
    {
        std::cout << *begin_it << " ";
        ++begin_it;
    }
    std::cout << std::endl;
}


// println: like Python's print with sep=" " and end="\n"
// useful for debugging bad sort functions
template <typename Head>
void println(const Head& head)
{
    std::cout << head << " " << "\n";
}

template <typename Head, typename ...Tail>
void println(const Head& head, const Tail&... tail)
{
    std::cout << head << " ";
    println(tail...);
}

// -- Sorts

// TODO: don't break this on empty vectors
template <typename ForwardIt>
void bubblesort(ForwardIt begin_it, ForwardIt end_it)
{
    auto did_swap = true;
    while (did_swap)
    {
        did_swap = false;
        for(auto i = begin_it; i + 1 != end_it; ++i)
        {
            if (*i > *(i + 1))
            {
                std::iter_swap(i, i + 1);
                did_swap = true;
            }
        }
    }
}


// I don't know the proper name for this, but the idea is to search to the end
// to find the max element, swap the max element with the end element, shrink
// the vector by one and repeat
template <typename BidirectionalIt>
void minskersort(BidirectionalIt begin_it, BidirectionalIt end_it)
{
    // TODO: don't make copies of the args

    auto last_it = end_it - 1;
    // NOTE: this is basically a pointer, right? So swapping the underlying
    // value shouldn't change the value of the iterator I think
    auto first_it = begin_it;
    while (last_it != first_it)
    {
        // init the max to the first value
        auto max_it = first_it;

        // TODO: off by 1 error?
        for(auto i = first_it; i != last_it + 1; ++i)
        {
            if (*i > *max_it)
            {
                max_it = i;
            }
        }

        std::iter_swap(max_it, last_it);

        --last_it;
    }
}


template <typename RandomAccessIt>
void quicksort(RandomAccessIt begin_it, RandomAccessIt end_it)
{
}

// -- Main Code

template<typename SortFunc>
void benchmark(const char* name, SortFunc sort_func, std::vector<data_type> v)
{
    using nanoseconds_t = std::chrono::duration < int, std::nano >;

    std::cout << "---" << std::endl;
    std::cout << name << std::endl;

    // print_container(v.begin(), v.end());

    //start time
    auto start = std::chrono::high_resolution_clock::now();

    sort_func(v.begin(), v.end());

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<nanoseconds_t>(end - start);

    // check it
    auto tmp = v;
    std::sort(tmp.begin(), tmp.end());
    assert(v == tmp);

    // print_container(v.begin(), v.end());

    println(duration.count(), "ns");
}

std::vector<int> make_random_vector(size_t size)
{
    std::mt19937 rng;
    rng.seed(std::random_device()());
    // std::uniform_int_distribution<decltype(rng)::result_type> dist(0, size -1);
    // TODO: use a size_t distribution?
    std::uniform_int_distribution<int> dist(0, static_cast<int>(size - 1));

    std::vector<int> v;
    v.reserve(size);
    for (size_t i = 0; i < size; ++i)
    {
        v.push_back(dist(rng));
    }

    return v;
}

int main()
{

    auto v = make_random_vector(40);

    // https://stackoverflow.com/a/47209691/2958070
    using iterator_type = decltype(v)::iterator;


    benchmark("bubblesort", bubblesort<iterator_type>, v);
    // // benchmark("quicksort", quicksort, v);
    // // benchmark("heapsort", heapsort, v);
    // // benchmark("mergesort", mergesort, v);
    // // benchmark("insertionsort", insertionsort, v);
    benchmark("minskersort", minskersort<iterator_type>, v);
}

@rayhamel thanks- I got a quick look at your code but I won't really be able to dig in until this weekend. It's not a school assignment, just a personal project, and I'm interested in the whole thing. In fact, the benchmarking code might be more practically beneficial than the sorting code :) . Once again, thanks! I'll probably add some comments there if I have questions