#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>

template<typename FwdIter>
void selection_sort(FwdIter beg, FwdIter end) {
    for(FwdIter i = beg; i != end; ++i)
        std::iter_swap(i, std::min_element(i, end));
}


template<typename RndIter>
void insertion_sort(RndIter beg, RndIter end)
{
    for (RndIter i = beg; i != end; ++i)
        std::rotate(std::upper_bound(beg, i, *i), i, i+1);
}

std::ostream& operator<<(std::ostream& os, const std::vector<int>& v)
{
    copy(v.begin(), v.end(), std::ostream_iterator<int>(os, " "));
    return os;
}

int main()
{
    std::vector<int> v(20, 1);
    partial_sum(v.begin(), v.end(), v.begin());

    random_shuffle(v.begin(), v.end());
    std::cout << "Before selection_sort: " << v << '\n';
    selection_sort(v.begin(), v.end());
    std::cout << "After selection_sort: " << v << '\n';

    random_shuffle(v.begin(), v.end());
    std::cout << "Before insertion_sort: " << v << '\n';
    insertion_sort(v.begin(), v.end());
    std::cout << "After insertion_sort: " << v << '\n';
}