#ifndef QUICK_SORT_Y_H #define QUICK_SORT_Y_H #include <cstddef> #include <algorithm> #include <functional> #include <iterator> // quick sort. (yane版挿入ソートをベース.. けどひどい状態に) template<typename BidiIte, class C> void quick_sort_y(BidiIte first, BidiIte last, C cmp) { typedef typename std::iterator_traits<BidiIte>::value_type T; using std::iter_swap; std::size_t size = std::size_t(std::distance(first, last)); if (size <= 32) { if (size <= 1) return; BidiIte i = first; for (;;) { BidiIte k = i; if (++i == last) return; if (!cmp(*i, *k)) continue; T tmp( *i ); BidiIte j = i; goto JJJ; do { --k; if (!cmp(tmp, *k)) break; JJJ: *j = *k; --j; } while (k != first); *j = tmp; } return; } BidiIte ite( first ); std::advance( ite, size / 2 ); const T m( *ite ); BidiIte l = first; BidiIte r = last; std::size_t lc = 0; std::size_t rc = size; for (;;) { while (cmp(*l, m)) ++l, ++lc; do { --r, --rc; } while (cmp(m, *r)); if (lc >= rc) break; iter_swap(l, r); ++l, ++lc; } quick_sort_y(first, l , cmp); quick_sort_y(l , last, cmp); } template<typename BidiIte> inline void quick_sort_y(BidiIte first, BidiIte last) { quick_sort_y( first, last, std::less<typename std::iterator_traits<BidiIte>::value_type>() ); } #endif // QUICK_SORT_H