gistfile1.cpp

#include <vector>
#include <algorithm>

template<class T>
class sorter_base{
public:
    sorter_base(std::vector<T> const& values_) : values(values_){}
    void set_values(std::vector<T> const& values_)
    {
        values = values_;
    }
    std::vector<T> get_values() const
    {
        return this->values;
    }
    virtual void sort() = 0;
    virtual ~sorter_base() = default;
protected:
    std::vector<T> values;
};

struct selection_sort_tag{};
struct bogo_sort_tag{};

template<class T, class Tag>
class sorter;

template<class T>
class sorter<T, selection_sort_tag> : public sorter_base<T>{
public:
    sorter(std::vector<T> const& v) : sorter_base<T>(v){}
    virtual void sort() override
    {
        for(auto ri=this->values.rbegin();ri!=this->values.rend(); ++ri){
            this->insert(ri);
        }
    }
private:
    template< class ReverseIter >
    void insert(ReverseIter last)
    {
        auto const val = *last;
        auto first = std::find(last+1, this->values.rbegin(), *last);
        std::move_backward(last+1, first, first-1);
        *first = val;
    }
};

template<class T>
class sorter<T, bogo_sort_tag> : public sorter_base<T>{
public:
    sorter(std::vector<T> const& v) : sorter_base<T>(v){}
    virtual void sort()
    {
        while( !std::is_sorted(std::begin(this->values), std::end(this->values)) ){
            std::random_shuffle(std::begin(this->values), std::end(this->values));
        }
    }
};

#include <iostream>
#include <iterator>

template<class Container>
void print(Container const& c)
{
    std::copy(c.begin(), c.end(), std::ostream_iterator<typename Container::value_type>(std::cout, " "));
    std::cout << '\n';
}

int main() {
    std::vector<int> v = {32, 71, 12, 45, 26, 80, 53, 33}; //C++11から配列的な初期化構文が使えるようになった
    print(v);

    {
        sorter<int, selection_sort_tag> s(v);
        s.sort();
        print(s.get_values());
    }

    {
        sorter<int, bogo_sort_tag> s(v);
        s.sort();
        print(s.get_values());
    }

    return 0;
}