sorting algorithm comparison in C++11

main.cpp

#include <vector>
#include <iostream>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <iterator>
#include <utility>
#include <cassert>
using namespace std;

struct counts {     // record the number of comparisons and exchanges during a sort
    size_t comp, exch;
    counts(size_t c = 0, size_t e = 0) : comp(c), exch(e) {}
    counts operator+(const counts &rhs) { return { comp + rhs.comp, exch + rhs.exch }; }
    bool compare(bool expr) { ++comp; return expr; }
    template<typename T> void exchange(T &a, T &b)  { ++exch; swap(a, b); }
};

template<typename RandomAccessIterator>
counts bubblesort(RandomAccessIterator begin, RandomAccessIterator end)
{
    counts c;
    do {
        auto newend = begin;
        for(auto i = begin + 1; i < end; ++i) {            
            if(c.compare(*(i - 1) > *i)) {
                c.exchange(*(i - 1), *i);
                newend = i;
            }
        }
        end = newend;
    } while(end != begin);
    return c;
}

template<typename RandomAccessIterator>
counts quicksort(RandomAccessIterator begin, RandomAccessIterator end)
{
    counts c;
    auto size = end - begin;
    if(size < 2)
        return c;
    auto pivot = *(begin + size / 2), left = begin, right = end - 1;
    while(left <= right) {
        while(c.compare(*left < pivot))
            ++left;
        while(c.compare(*right > pivot))
            --right;
        if(left <= right) {
            c.exchange(*left, *right);
            ++left;
            --right;
        }
    }
    return c + quicksort(begin, right + 1) + quicksort(left, end);
}

template<typename RandomAccessIterator>
static counts heap_sift_down(RandomAccessIterator begin, size_t root, size_t size)
{
    counts c;
    while(root * 2 + 1 < size) {
        auto child = root * 2 + 1;
        
        if(child + 1 < size && c.compare(*(begin + child) < *(begin + child + 1)))
            ++child;
        if(c.compare(*(begin + root) < *(begin + child))) {
            c.exchange(*(begin + root), *(begin + child));
            root = child;
        } else
            break;
    }
    return c;
}

template<typename RandomAccessIterator>
counts heapsort(RandomAccessIterator begin, RandomAccessIterator end)
{
    counts c;
    auto size = end - begin;
    if(size < 2)
        return c;

    for(auto start = (size - 2) / 2; start >= 0; --start)           // heapify
        c = c + heap_sift_down(begin, start, size);

    while(--end > begin) {                                          // heap_sort    
        c.exchange(*end, *begin);
        c = c + heap_sift_down(begin, 0, end - begin);
    }
    return c;
}

template<typename T>
void evaluate_algorithms(const string &desc, const vector<T> &v)
{
    struct result { string name; counts cnt; };
    vector<T> ref(v), b(v), q(v), h(v);
    vector<result> results = { { "bubblesort", bubblesort(begin(b), end(b)) },
                               { "quicksort",  quicksort(begin(q), end(q))  },
                               { "heapsort",   heapsort(begin(h), end(h))   } };

    sort(begin(ref), end(ref));     // reference sort by standard library implementation
    assert(ref == b && ref == q && ref == h);
    
    auto best_comp = min_element(begin(results), end(results),
            [](const result &a, const result &b) { return a.cnt.comp < b.cnt.comp; });
    auto best_exch = min_element(begin(results), end(results),
            [](const result &a, const result &b) { return a.cnt.exch < b.cnt.exch; });
    
    cout << desc << endl;
    for(auto &r : results)
        cout << "  "
             << setw(10) << right << r.name << ": "
             << setw(5)  << right << r.cnt.comp << " comparisons" << setw(8) << left << ((&r == &*best_comp) ? "<--BEST" : "")
             << setw(5)  << right << r.cnt.exch << " exchanges"   << setw(8) << left << ((&r == &*best_exch) ? "<--BEST" : "")
             << endl;
    cout << endl;
}

template<typename T>
vector<T> read_len_prefixed_list(istream &stream)
{
    vector<T> v;
    size_t len;
    stream >> len;
    copy_n(istream_iterator<T>(stream), len, back_inserter(v));
    stream.ignore(numeric_limits<streamsize>::max(), '\n');
    return v;
}

int main()
{
    string desc;
    while(getline(cin, desc))
        evaluate_algorithms(desc, read_len_prefixed_list<int>(cin));
}

output.txt

$ g++ -W{all,extra,error} -pedantic -g -O2 -std=c++11 -D_GLIBCXX_DEBUG main.cpp -o main && main <testdata.txt
10 numbers in almost sorted order
  bubblesort:    30 comparisons<--BEST    10 exchanges
   quicksort:    39 comparisons            6 exchanges<--BEST
    heapsort:    40 comparisons           30 exchanges

10 numbers in random order
  bubblesort:    45 comparisons           25 exchanges
   quicksort:    45 comparisons           12 exchanges<--BEST
    heapsort:    42 comparisons<--BEST    27 exchanges

10 numbers in reverse order
  bubblesort:    45 comparisons           45 exchanges
   quicksort:    34 comparisons<--BEST    11 exchanges<--BEST
    heapsort:    35 comparisons           21 exchanges

50 numbers in almost sorted order
  bubblesort:   595 comparisons           47 exchanges
   quicksort:   259 comparisons<--BEST    28 exchanges<--BEST
    heapsort:   438 comparisons          269 exchanges

50 numbers in random order
  bubblesort:  1144 comparisons          594 exchanges
   quicksort:   387 comparisons<--BEST    78 exchanges<--BEST
    heapsort:   423 comparisons          246 exchanges

50 numbers in reverse order
  bubblesort:  1225 comparisons         1225 exchanges
   quicksort:   258 comparisons<--BEST    55 exchanges<--BEST
    heapsort:   379 comparisons          207 exchanges

100 numbers in almost sorted order
  bubblesort:  2140 comparisons          124 exchanges
   quicksort:   664 comparisons<--BEST    66 exchanges<--BEST
    heapsort:  1086 comparisons          638 exchanges

100 numbers in random order
  bubblesort:  4712 comparisons         2175 exchanges
   quicksort:   824 comparisons<--BEST   186 exchanges<--BEST
    heapsort:  1053 comparisons          599 exchanges

100 numbers in reverse order
  bubblesort:  4950 comparisons         4950 exchanges
   quicksort:   610 comparisons<--BEST   112 exchanges<--BEST
    heapsort:   944 comparisons          516 exchanges

testdata.txt

10 numbers in almost sorted order
10
1
2
6
4
5
3
10
8
9
7
10 numbers in random order
10
5
9
8
1
6
3
4
10
7
2
10 numbers in reverse order
10
10
9
8
7
6
5
4
3
2
1
50 numbers in almost sorted order
50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
26
18
19
20
21
25
23
24
22
17
27
28
29
30
31
32
33
34
35
36
50
38
39
40
41
42
43
44
45
46
47
48
49
37
50 numbers in random order
50
33
45
17
13
1
5
25
24
10
11
50
49
32
7
37
18
35
19
48
38
12
44
6
27
43
3
9
22
20
40
31
39
21
23
41
42
4
47
8
46
28
34
14
29
15
16
2
30
26
36
50 numbers in reverse order
50
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
100 numbers in almost sorted order
100
0
2
3
36
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
4
37
38
39
40
41
42
43
44
50
46
47
48
49
45
51
52
53
54
55
56
57
58
59
60
61
62
63
64
69
66
67
68
65
70
71
72
73
74
75
99
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
76
100
100 numbers in random order
100
1
34
24
94
58
45
36
35
8
40
48
88
53
29
6
14
67
12
79
20
27
3
95
72
9
13
62
70
78
47
19
23
57
68
82
30
87
44
81
64
46
75
96
5
22
52
25
32
69
100
31
41
42
84
66
39
83
37
17
90
38
76
18
10
71
7
74
55
54
89
65
98
97
2
59
51
21
93
4
60
92
43
80
61
16
99
85
49
15
63
91
28
56
33
86
11
50
26
73
77
100 numbers in reverse order
100
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1