2
\$\begingroup\$

I have written a program with the goal of comparing the speed of some common sorting algorithms. It works with many data types.

#include <algorithm> // std::find_if
#include <boost/program_options.hpp>
#include <exception> // std::exception
#include <iomanip> // std::setew
#include <iostream>
#include <limits> // std::numeric_limits
#include <random>
#include <tuple>
#include <type_traits> // std::is_floating_point
#include <utility> //std::reference_wrapper, std::binary_function
#include <vector>

template<typename VT>
struct program_args {
    // general
    bool help, quiet, time;
    int prec = std::numeric_limits<VT>::max_digits10;
    long long avg, avg_count = 0;
    std::string delim;

    // fill
    std::vector<VT> list;
    long long fill_rand, fill_forward = 0, fill_backward = 0;
    VT fill_rand_lower, fill_rand_upper, fill_increment;

    // algorithm
    bool alg_all;
    std::vector<std::string> alg_except;

    typedef typename std::tuple<const std::string, const std::string, double, bool> TUP;

    TUP bogosort = mt("bogosort", "Bogosort: "),
        bubble_sort = mt("bubble-sort", "Bubble Sort: "),
        cocktail_sort = mt("cocktail-sort", "Cocktail Sort: "),
        gnome_sort = mt("gnome-sort", "Gnome Sort: "),
        heap_sort = mt("heap-sort", "Heap Sort: "),
        insertion_sort = mt("insertion-sort", "Insertion Sort: "),
        merge_sort = mt("merge-sort", "Merge Sort: "),
        permutation_sort = mt("permutation-sort", "Permutation Sort: "),
        quick_sort = mt("quick-sort", "Quick Sort: "),
        selection_sort = mt("selection-sort", "Selection Sort: ");

    const std::vector<std::reference_wrapper<TUP> > algs = {
        bogosort,
        bubble_sort,
        cocktail_sort,
        gnome_sort,
        heap_sort,
        insertion_sort,
        merge_sort,
        permutation_sort,
        quick_sort,
        selection_sort
    };

    const int mstr = static_cast<int>(max_strlen(algs));

    private:
        TUP mt(const std::string & str1, const std::string & str2,
            const double & sum = 0.0, const bool & use = false) {
            return std::make_tuple(str1, str2, sum, use);
        }

        template<typename T>
        std::size_t max_strlen(const T & vect) {
            std::size_t len = 0;
            for(const auto & i : vect) {
                std::size_t j = std::get<1>(i.get()).length();
                len = (j > len) ? j : len;
            }
            return len;
        }
};

enum returnID {
    success_help = -1,
    success = 0,

    prec_under = 1,
    prec_over = 2,

    avg_under = 3,

    fill_rand_under = 4,
    fill_forward_under = 5,
    fill_backward_under = 6,

    alg_empty = 7,
    alg_invalid = 8,

    known_err = 9,
    other_err = 10
};

void conflicting_opts(const boost::program_options::variables_map & vm, 
    const std::string & opt1, const std::string & opt2) {
    if(vm.count(opt1) && !vm[opt1].defaulted()
        && vm.count(opt2) && !vm[opt2].defaulted())
        throw std::logic_error(std::string("Conflicting options: '--")
            + opt1 + "' and '--" + opt2 + "'.");
}

template<typename VT>
returnID parse_args(program_args<VT> & args, const int & argc, char const * const * argv) {
    namespace po = boost::program_options;

    po::options_description general("General options");
    general.add_options()
        ("help", po::bool_switch(&args.help),
            "produce this help message")
        ("quiet", po::bool_switch(&args.quiet),
            "disable printing sorted list")
        ("time", po::bool_switch(&args.time),
            "print CPU time for each algorithm")
        ("prec", po::value<int>(&args.prec)->default_value(args.prec),
            "set OUTPUT precision")
        ("avg", po::value<long long>(&args.avg)->default_value(1),
            "rerun sorting a specified number times on the same list")
        ("delim", po::value<std::string>(&args.delim)->default_value(" "),
            "delimiters used when printing lists, "
            "wrap in quotation marks, escape characters as needed");

    po::options_description fill("Fill options");
    fill.add_options()
        ("list", po::value<std::vector<VT> >(&args.list)->multitoken(),
            "input a list of values")
        ("fill-rand", po::value<long long>(&args.fill_rand)->default_value(10),
            "fill the list random numbers")
        ("rand-lower", po::value<VT>(&args.fill_rand_lower)->default_value(-10),
            "specify the lower bound for '--fill-rand'")
        ("rand-upper", po::value<VT>(&args.fill_rand_upper)->default_value(10),
            "specify the upper bound for '--fill-rand'")
        ("fill-forward", po::value<long long>(&args.fill_forward),
            "fill the list with incrementing numbers")
        ("fill-backward", po::value<long long>(&args.fill_backward),
            "fill the list with decrementing numbers")
        ("fill-increment", po::value<VT>(&args.fill_increment)->default_value(1),
            "specify the fill increment used with '--fill-forward' and '--fill-backward'");

    po::options_description algorithm("Algorithm options");
    algorithm.add_options()
        ("alg-all", po::bool_switch(&args.alg_all),
            "use all available algorithms")
        ("alg-except", po::value<std::vector<std::string> >(&args.alg_except)->multitoken(),
            "except algorithms when using '--alg-all', wrap each argument in quotation marks")
        ("alg-bogosort", po::bool_switch(&std::get<3>(args.bogosort)),
            "use the bogosort algorithm")
        ("alg-bubble-sort", po::bool_switch(&std::get<3>(args.bubble_sort)),
            "use the bubble sort algorithm")
        ("alg-cocktail-sort", po::bool_switch(&std::get<3>(args.cocktail_sort)),
            "use the cocktail shaker sort")
        ("alg-gnome-sort", po::bool_switch(&std::get<3>(args.gnome_sort)),
            "use the gnome sort algorithm")
        ("alg-heap-sort", po::bool_switch(&std::get<3>(args.heap_sort)),
            "use the heap sort algorithm")
        ("alg-insertion-sort", po::bool_switch(&std::get<3>(args.insertion_sort)),
            "use the insertion sort algorithm")
        ("alg-merge-sort", po::bool_switch(&std::get<3>(args.merge_sort)),
            "use the merge sort algorithm")
        ("alg-permutation-sort", po::bool_switch(&std::get<3>(args.permutation_sort)),
            "use the permutation sort algorithm")
        ("alg-quick-sort", po::bool_switch(&std::get<3>(args.quick_sort)),
            "use the quick sort algorithm")
        ("alg-selection-sort", po::bool_switch(&std::get<3>(args.selection_sort)),
            "use the selection sort algorithm");

    po::options_description all("Allowed options");
    all.add(general).add(fill).add(algorithm);

    po::variables_map vm;
    po::store(parse_command_line(argc, argv, all, po::command_line_style::unix_style 
        ^ po::command_line_style::allow_short), vm);
    po::notify(vm);

    if(args.help) {
        std::cout << all << '\n';
        return returnID::success_help;
    }

    // general
    if(args.prec < 0) {
        std::cerr << "error: '--prec' cannot be < 0\n";
        return returnID::prec_under;

    } else if(args.prec > std::numeric_limits<VT>::max_digits10) {
        std::cerr << "error: '--prec' cannot be greater than the data type's precision ("
            << std::numeric_limits<VT>::max_digits10 << ")\n";
        return returnID::prec_over;
    }

    if(args.avg <= 0) {
        std::cerr << "error: '--avg' cannot be <= 0\n";
        return returnID::avg_under;
    }

    // fill
    conflicting_opts(vm, "list", "fill-rand");
    conflicting_opts(vm, "list", "fill-forward");
    conflicting_opts(vm, "list", "fill-backward");
    conflicting_opts(vm, "list", "fill-increment");

    conflicting_opts(vm, "fill-rand", "fill-forward");
    conflicting_opts(vm, "fill-rand", "fill-backward");
    conflicting_opts(vm, "fill-rand", "fill-increment");

    conflicting_opts(vm, "fill-forward", "fill-backward");

    if(args.fill_rand < 0) {
        std::cerr << "error: '--fill-rand' must be >= 0\n";
        return returnID::fill_rand_under;
    } else if(vm.count("fill-rand") && !vm.count("fill-forward") && !vm.count("fill-backward")) {
        fill_rand(args);
    }

    if(args.fill_forward < 0) {
        std::cerr << "error: '--fill-forward' must be >= 0\n";
        return returnID::fill_forward_under;
    } else if(vm.count("fill-forward")) {
        fill_forward(args);
    }

    if(args.fill_backward < 0) {
        std::cerr << "error: 'fill-backward' must be >= 0\n";
        return returnID::fill_backward_under;
    } else if(vm.count("fill-backward")) {
        fill_backward(args);
    }

    // algorithm
    for(auto & i : args.algs) {
        conflicting_opts(vm, "alg-except", "alg-" + std::get<0>(i.get()));
    }

    for(const auto & i : args.alg_except) {
        if(i.compare(0, 2, "--") == 0) {
            std::cerr << "error: the required argument for option '--alg-except' is missing\n";
            return returnID::alg_empty;
        }
        if(std::find_if(args.algs.begin(), args.algs.end(),
            [i](const auto & e) { return std::get<0>(e.get()) == i; }) == args.algs.end()) {
            std::cerr << "error: the argument ('"
                << i << "') for option '--alg-except' is invalid\n";
            return returnID::alg_invalid;   
        }
    }

    return returnID::success;
}

template<typename VT>
void printVect(const std::vector<VT> & list, const int & prec, const std::string & delim) {
    std::cout.precision(prec);
    for(const VT & i : list) {
        std::cout << std::fixed << i << delim;
    }
}

// begin: helpers
template<typename Order>
struct non_strict_op:
    std::binary_function<typename Order::second_argument_type,
        typename Order::first_argument_type, bool> {
            non_strict_op(Order o): order(o) {}
            bool operator()(typename Order::second_argument_type arg1,
                typename Order::first_argument_type arg2) const {
                    return !order(arg2, arg1);
                }
    private:
        Order order;
};

template<typename Order> non_strict_op<Order> non_strict(Order o) {
    return non_strict_op<Order>(o);
}
// end: helpers

// begin: algorithms
template<typename It>
void bogosort(It first, It last) {
    std::mt19937 generator{std::random_device{}()};
    while(!std::is_sorted(first, last, 
        std::less<typename std::iterator_traits<It>::value_type>())) {
        std::shuffle(first, last, generator);
    }
}

template<typename It>
void bubble_sort(It first, It last) {
    bool swapped = true;
    while(first != last-- && swapped) {
        swapped = false;
        for(auto i = first; i != last; ++i) {
            if(*(i + 1) < *i) {
                std::iter_swap(i, i + 1);
                swapped = true;
            }
        }
    }
}

template<typename It>
void cocktail_sort(It first, It last) {
    bool swapped = true;
    while(first != last-- && swapped) {
        swapped = false;
        for(auto i = first; i != last; ++i) {
            if(*(i + 1) < *i) {
                std::iter_swap(i, i + 1);
                swapped = true;
            }
        }
        if(!swapped) break;
        swapped = false;
        for(auto i = last - 1; i != first; --i) {
            if(*i < *(i - 1)) {
                std::iter_swap(i, i - 1);
                swapped = true;
            }
        }
        ++first;
    }
}

template<typename It>
void gnome_sort(It first, It last) {
    auto i = first + 1;
    auto j = first + 2;
    while(i < last) {
        if(!(*i < *(i - 1))) {
            i = j;
            ++j;
        } else {
            std::iter_swap(i - 1, i);
            --i;
            if(i == first) {
                i = j;
                ++j;
            }
        }
    }
}

template<typename It>
void heap_sort(It first, It last) {
    std::make_heap(first, last);
    std::sort_heap(first, last);
}

template<typename It>
void insertion_sort(It first, It last) {
    for(auto i = first; i != last; ++i) {
        std::rotate(std::upper_bound(first, i, *i,
            std::less<typename std::iterator_traits<It>::value_type>()), i, i + 1);
    }
}

template<typename It>
void merge_sort(It first, It last) {
    if(last - first > 1) {
        It middle = first + (last - first) /  2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}

template<typename It>
void permutation_sort(It first, It last) {
    while(std::next_permutation(first, last)) {}
}

template<typename It>
 void quick_sort(It first, It last)
{
  if (first != last && first+1 != last)
  {
    typedef typename std::iterator_traits<It>::value_type value_type;
    It mid = first + (last - first)/2;

    // median of 3
    value_type pivot = std::max(std::min(*first, *mid), 
        std::min(std::max(*first, *mid), *(last-1)));

    It split1 = std::partition(first, last, 
        std::bind2nd(std::less<value_type>(), pivot));
    It split2 = std::partition(split1, last, 
        std::bind2nd(non_strict(std::less<value_type>()), pivot));
    quick_sort(first, split1);
    quick_sort(split2, last);
  }
}

template<typename It>
void selection_sort(It first, It last) {
    for(auto i = first; i != last; ++i) {
        std::iter_swap(i, std::min_element(i, last));
    }
}
// end: algorithms

template<typename T>
bool contains(const std::vector<T> & vect, const std::string & alg) {
    return std::find(vect.begin(), vect.end(), alg) != vect.end();
}

template<typename VT, typename FT>
void sort(const program_args<VT> & args, FT && sorter, const std::string & msg, double & sum) {
    auto list_cp = args.list;

    std::clock_t tstart = clock();

    static_cast<FT &&>(sorter)(list_cp.begin(), list_cp.end());

    const double time = (double)(clock() - tstart) / CLOCKS_PER_SEC;
    sum += time;

    if(!args.quiet && (args.avg == 1 || args.avg_count == (args.avg - 1)))
        std::cout << "\n\n";

    if(args.avg == 1 || args.avg_count == (args.avg - 1))
        std::cout << std::left << std::setw(args.mstr) << msg;

    if(args.time && args.avg == 1) {
        std::cout.precision(6);
        std::cout << std::fixed << "CPU time: " << time << " s";
    } else if(args.time && args.avg_count == (args.avg - 1)) {
        std::cout.precision(6);
        std::cout << std::fixed << "Average CPU time: " << sum / (double)(args.avg) << " s";
    } 

    if (args.avg == 1 || args.avg_count == (args.avg - 1)) {
        std::cout << '\n';
    }

    if(!args.quiet && (args.avg == 1 || args.avg_count == (args.avg - 1))) {
        printVect(list_cp, args.prec, args.delim);
    }
}

// begin: fillers
template<typename VT>
void fill_rand(program_args<VT> & args) {
    typedef typename std::conditional<std::is_floating_point<VT>::value,
        std::uniform_real_distribution<VT>,
        std::uniform_int_distribution<VT> >::type DIST;

    std::mt19937 generator{std::random_device{}()};
    DIST dis{args.fill_rand_lower, args.fill_rand_upper};

    for(long long i = 0; i < args.fill_rand; ++i)
        args.list.push_back(dis(generator));
}

template<typename VT>
void fill_forward(program_args<VT> & args) {
    VT count = 0;
    for(long long i = 0; i < args.fill_forward; ++i, count += args.fill_increment)
        args.list.push_back(count);
}

template<typename VT>
void fill_backward(program_args<VT> & args) {
    VT count = 0;
    for(long long i = 0; i < args.fill_backward; ++i, count += args.fill_increment)
        args.list.insert(args.list.begin(), count);
}
// end: fillers

int main(int argc, char * argv[]) {
    try {
        // change to required type
        program_args<long double> args;

        switch(auto result = parse_args(args, argc, argv)) {
            case returnID::success: break;
            case returnID::success_help: return 0;
            default: return result;
        }

        if(!args.quiet) {
            std::cout << "Before:\n";
            printVect(args.list, args.prec, args.delim);
        }

        typedef typename std::vector<decltype(args.list)::value_type>::iterator IT;

        std::vector<std::function<void(IT, IT)> > lambs = {
            [](auto f, auto l) { bogosort(f, l);},
            [](auto f, auto l) { bubble_sort(f, l);},
            [](auto f, auto l) { cocktail_sort(f, l);},
            [](auto f, auto l) { gnome_sort(f, l);},
            [](auto f, auto l) { heap_sort(f, l);},
            [](auto f, auto l) { insertion_sort(f, l);},
            [](auto f, auto l) { merge_sort(f, l);},
            [](auto f, auto l) { permutation_sort(f, l);},
            [](auto f, auto l) { quick_sort(f, l);},
            [](auto f, auto l) { selection_sort(f, l);}
        };

        for(; args.avg_count < args.avg; ++args.avg_count) {
            long long i = 0;

            for(const auto & j : args.algs) {
                if((args.alg_all || std::get<3>(j.get()))
                    && !contains(args.alg_except, std::get<0>(j.get()))) {
                    sort(args, lambs[i], std::get<1>(j.get()), std::get<2>(j.get()));
                }
                ++i;
            }
        }

        if(!args.quiet) std::cout << '\n';

        return returnID::success;
    } catch(std::exception & e) {
        std::cerr << "error: " << e.what() << '\n';
        return returnID::known_err;
    } catch(...) {
        std::cerr << "error: exception of unknown type!\n";
        return returnID::other_err;
    }
}

View on GitHub

Compilation and testing

Compiled with GCC 7.2.1 using

g++ -o compsort -Wall -Wextra -Wconversion -pedantic-errors -lboost_program_options compsort.cpp

Tested with Valgrind using -v --track-origins=yes, resulting in 0 errors and no leaks possible.

Help text

Allowed options:

General options:
  --help                     produce this help message
  --quiet                    disable printing sorted list
  --time                     print CPU time for each algorithm
  --prec arg (=21)           set OUTPUT precision
  --avg arg (=1)             rerun sorting a specified number times on the same
                             list
  --delim arg (= )           delimiters used when printing lists, wrap in 
                             quotation marks, escape characters as needed

Fill options:
  --list arg                 input a list of values
  --fill-rand arg (=10)      fill the list random numbers
  --rand-lower arg (=-10)    specify the lower bound for '--fill-rand'
  --rand-upper arg (=10)     specify the upper bound for '--fill-rand'
  --fill-forward arg         fill the list with incrementing numbers
  --fill-backward arg        fill the list with decrementing numbers
  --fill-increment arg (=1)  specify the fill increment used with 
                             '--fill-forward' and '--fill-backward'

Algorithm options:
  --alg-all                  use all available algorithms
  --alg-except arg           except algorithms when using '--alg-all', wrap 
                             each argument in quotation marks
  --alg-bogosort             use the bogosort algorithm
  --alg-bubble-sort          use the bubble sort algorithm
  --alg-cocktail-sort        use the cocktail shaker sort
  --alg-gnome-sort           use the gnome sort algorithm
  --alg-heap-sort            use the heap sort algorithm
  --alg-insertion-sort       use the insertion sort algorithm
  --alg-merge-sort           use the merge sort algorithm
  --alg-permutation-sort     use the permutation sort algorithm
  --alg-quick-sort           use the quick sort algorithm
  --alg-selection-sort       use the selection sort algorithm

The Algorithms

A majority of the code for the sorting comes from Rosetta Code. I did not feel that it was appropriate, nor necessary, to reinvent the wheel. I made changes to most of the sorting code: removing helper functions, improving performance, cleaning up namespaces, etc. Everything else is my own work.

Examples

./compsort --alg-all --prec 0 --fill-forward 5 --time --avg 5

Sorting a list that's already sorted:

Before:
0 1 2 3 4 

Bogosort:         Average CPU time: 0.000017 s
0 1 2 3 4 

Bubble Sort:      Average CPU time: 0.000001 s
0 1 2 3 4 

Cocktail Sort:    Average CPU time: 0.000000 s
0 1 2 3 4 

Gnome Sort:       Average CPU time: 0.000000 s
0 1 2 3 4 

Heap Sort:        Average CPU time: 0.000003 s
0 1 2 3 4 

Insertion Sort:   Average CPU time: 0.000001 s
0 1 2 3 4 

Merge Sort:       Average CPU time: 0.000002 s
0 1 2 3 4 

Permutation Sort: Average CPU time: 0.000014 s
0 1 2 3 4 

Quick Sort:       Average CPU time: 0.000001 s
0 1 2 3 4 

Selection Sort:   Average CPU time: 0.000001 s
0 1 2 3 4 

./compsort --alg-all --alg-except bogosort permutation-sort --quiet --time --fill-rand 1000 --avg 100

Sorting a list of 1000 random numbers averaged over 100 times, without using bogosort and permutation sort:

Bubble Sort:      Average CPU time: 0.020042 s
Cocktail Sort:    Average CPU time: 0.016162 s
Gnome Sort:       Average CPU time: 0.012508 s
Heap Sort:        Average CPU time: 0.000535 s
Insertion Sort:   Average CPU time: 0.000893 s
Merge Sort:       Average CPU time: 0.000453 s
Quick Sort:       Average CPU time: 0.000427 s
Selection Sort:   Average CPU time: 0.008818 s

Note: Bogosort and permutation sort are incredibly slow for larger lists, this is because of how they sort. Permutation is a variation of bogosort which goes through each iterative permutation of the list until it is sorted, whereas bogosort randomly permutes the list.

Problems

  1. Currently, I use a tuple to store info on each sorting algorithm: internal name, printed name, sum for --avg, and a usage Boolean. I store those tuples in a reference wrapped vector, to allow for iteration.

    Then, I have another vector in main() that stores the lambdas used to actually refer to the sorting functions.

    The problem: No matter what I try, I cannot find a way to put those lambdas (in lambs) in the initial tuples in program_args. I am not sure if this is even possible, honestly.

  2. Where should I be using std::size_t? I compile using -Wconversion to check for implicit type conversion, and I get no errors — does that mean I am good to go?

  3. Is there any undefined behavior, or uncaught errors? I thoroughly checked my code, but another pair of eyes are helpful with this kind of thing.

  4. How can I clean up my helpers? It seems messy to have a struct non_strict_op with a function non_strict, and so on — only used for quick_sort().

  5. Can I speed up any of my sorting implementations?

  6. Is my code easy to read? Do I need to rearrange anything?

  7. How can I improve general performance, is there something I am doing horribly wrong, or at least horribly inefficiently?

I am sure that I need more explanation, if something is unclear, please ask so I can clarify.

\$\endgroup\$
  • 1
    \$\begingroup\$ In bubble and cocktail sort, while changing the number of neither comparisons nor assignments, shouldn't that be first != --last? I'm not overly concerned with quicksort's worst case time consumption, but I prefer to iterate on the bigger partition to preclude O(n) space consumption. I use to harp about commenting what's not obvious, didn't see any (more) need even when checking for it - consider that a congratulation on readability. \$\endgroup\$ – greybeard Oct 1 '17 at 21:34
  • \$\begingroup\$ @greybeard You're right! I changed it to pre-increment last and it actually improved sorting performance. On average, bubble sort ended up being 0.5% faster and cocktail sort was 5% faster, I'll take it! \$\endgroup\$ – esote Oct 1 '17 at 22:53
  • \$\begingroup\$ @greybeard A little late, but using --last results in a segmentation fault when sorting an empty list (i.e. --fill-rand 0). \$\endgroup\$ – esote Oct 9 '17 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.