東方算程譚

template<typename InputIterator>
void selection_sort(InputIterator first, InputIterator last) {
    while ( first != last ) {
        iter_swap(first, min_element(first,last));
        ++first;
    }
}

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <cassert>

#include <tbb/tick_count.h> // tick_count
#include <tbb/task.h>       // task

using namespace std;

template<typename InputIterator> inline
bool is_sorted(InputIterator first, InputIterator last) {
    return adjacent_find(first, last, greater<iterator_traits<InputIterator>::value_type>()) == last;
}

// 単純選択ソート
template<typename InputIterator>
void selection_sort(InputIterator first, InputIterator last) {
    while ( first != last ) {
        iter_swap(first, min_element(first,last));
        ++first;
    }
}

class sort_task : public tbb::task {
public:
    typedef vector<string>::iterator iterator;
    typedef vector<string>::difference_type difference_type;
protected:
    iterator first;
    iterator last;
    static difference_type cutoff;
public:
    sort_task(iterator f, iterator l) : first(f), last(l) {}
    task* execute() {
        difference_type size = distance(first,last);
        // 要素数が cutoff 未満なら素直にselection_sort
        if ( size < cutoff ) {
            selection_sort(first, last);
        } // さもなくば
        else {
            iterator mid = first;
            advance(mid, size/2);
            // [first,mid) : 小さい要素群 と [mid,last) : 大きい要素群 に振り分けて
            nth_element(first, mid, last);
            // それぞれをソートするtaskを作り
            task* left_task = new( allocate_child() ) sort_task(first, mid);
            task* right_task = new( allocate_child() ) sort_task(mid, last);
            // 双方を起動して完了を待つ
            set_ref_count(3);
            spawn(*left_task);
            spawn_and_wait_for_all(*right_task);
        }
        return 0;
    }
};

sort_task::difference_type sort_task::cutoff = 30;

int main() {

    vector<string> source;
    {
        string value = "ABCDEFGH";
        do {
            source.push_back(value);
        } while ( next_permutation(value.begin(), value.end()) );
        assert( is_sorted(source.begin(), source.end()) );
        random_shuffle(source.begin(), source.end());
    }

    {
        cout << "quick sort ... " << flush;
        vector<string> input = source;
        tbb::tick_count t = tbb::tick_count::now();
        sort(input.begin(), input.end());
        cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
        assert( is_sorted(input.begin(), input.end()) );
    }

    {
        cout << "selection_sort ... " << flush;
        vector<string> input = source;
        tbb::tick_count t = tbb::tick_count::now();
        selection_sort( input.begin(), input.end());
        cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
        assert( is_sorted(input.begin(), input.end()) );
    }

    {
        cout << "sort_task ... " << flush;
        vector<string> input = source;
        tbb::task* tsk = new(tbb::task::allocate_root()) sort_task(input.begin(), input.end());
        tbb::tick_count t = tbb::tick_count::now();
        tbb::task::spawn_root_and_wait(*tsk);
        cout << (tbb::tick_count::now() - t).seconds() << " [sec]\n";
        assert( is_sorted(input.begin(), input.end()) );
    }

}