2014-11に記述,quick_sortの独自実装

quick_sort.cpp

// -*- flycheck-clang-language-standard : "c++14"; -*-
// clang++ -std=c++14 -stdlib=libc++
// clang version 3.5.0 (tags/RELEASE_350/final)
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <vector>

namespace reinvention
{
    template<typename I>
    constexpr bool helper_is_sorted(const I begin, const I end)
    {
        return (begin != (end - 1)) ?
            (*begin < *(begin + 1)) ?
            reinvention::helper_is_sorted(begin + 1, end) :
            false :
            true;
    }

    template<typename I>
    constexpr bool is_sorted(const I begin, const I end)
    {
        return (begin != end) ?
            reinvention::helper_is_sorted(begin, end) :
            true;
    }

    template<typename I>
    constexpr void quick_sort(I begin, I end)
    {
        using T = typename std::iterator_traits<I>::value_type;
        if(!reinvention::is_sorted(begin, end))
        {
            const T pivot = *begin;

            std::vector<T> left;
            std::copy_if(begin + 1, end, std::back_inserter(left),
                         [&pivot](const T& x)
                         {
                             return x < pivot;
                         });
            reinvention::quick_sort(left.begin(), left.end());

            std::vector<T> right;
            std::copy_if(begin + 1, end, std::back_inserter(right),
                         [&pivot](const T& x)
                         {
                             return pivot < x;
                         });
            reinvention::quick_sort(right.begin(), right.end());

            auto step = std::copy(left.begin(), left.end(), begin);
            *step++ = pivot;
            std::copy(right.begin(), right.end(), step);
        }
    }
}

int main()
{
    std::array<double, 10> sec;
    std::for_each(sec.begin(), sec.end(), [](double& x){std::cin >> x;});

    reinvention::quick_sort(sec.begin(), sec.end());

    std::for_each(sec.begin(), sec.end(), [](const double x){std::cout << x << std::endl;});
}