boost/move/algo/detail/pdqsort.hpp
////////////////////////////////////////////////////////////////////////////// // // (C) Copyright Orson Peters 2017. // (C) Copyright Ion Gaztanaga 2017-2018. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // See http://www.boost.org/libs/move for documentation. // ////////////////////////////////////////////////////////////////////////////// // // This implementation of Pattern-defeating quicksort (pdqsort) was written // by Orson Peters, and discussed in the Boost mailing list: // http://boost.2283326.n4.nabble.com/sort-pdqsort-td4691031.html // // This implementation is the adaptation by Ion Gaztanaga of code originally in GitHub // with permission from the author to relicense it under the Boost Software License // (see the Boost mailing list for details). // // The original copyright statement is pasted here for completeness: // // pdqsort.h - Pattern-defeating quicksort. // Copyright (c) 2015 Orson Peters // This software is provided 'as-is', without any express or implied warranty. In no event will the // authors be held liable for any damages arising from the use of this software. // Permission is granted to anyone to use this software for any purpose, including commercial // applications, and to alter it and redistribute it freely, subject to the following restrictions: // 1. The origin of this software must not be misrepresented; you must not claim that you wrote the // original software. If you use this software in a product, an acknowledgment in the product // documentation would be appreciated but is not required. // 2. Altered source versions must be plainly marked as such, and must not be misrepresented as // being the original software. // 3. This notice may not be removed or altered from any source distribution. // ////////////////////////////////////////////////////////////////////////////// #ifndef BOOST_MOVE_ALGO_PDQSORT_HPP #define BOOST_MOVE_ALGO_PDQSORT_HPP #ifndef BOOST_CONFIG_HPP # include <boost/config.hpp> #endif # #if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include <boost/move/detail/config_begin.hpp> #include <boost/move/detail/workaround.hpp> #include <boost/move/utility_core.hpp> #include <boost/move/algo/detail/insertion_sort.hpp> #include <boost/move/algo/detail/heap_sort.hpp> #include <boost/move/detail/iterator_traits.hpp> #include <boost/move/adl_move_swap.hpp> #include <cstddef> namespace boost { namespace movelib { namespace pdqsort_detail { //A simple pair implementation to avoid including <utility> template<class T1, class T2> struct pair { pair() {} pair(const T1 &t1, const T2 &t2) : first(t1), second(t2) {} T1 first; T2 second; }; enum { // Partitions below this size are sorted using insertion sort. insertion_sort_threshold = 24, // Partitions above this size use Tukey's ninther to select the pivot. ninther_threshold = 128, // When we detect an already sorted partition, attempt an insertion sort that allows this // amount of element moves before giving up. partial_insertion_sort_limit = 8, // Must be multiple of 8 due to loop unrolling, and < 256 to fit in unsigned char. block_size = 64, // Cacheline size, assumes power of two. cacheline_size = 64 }; // Returns floor(log2(n)), assumes n > 0. template<class Unsigned> Unsigned log2(Unsigned n) { Unsigned log = 0; while (n >>= 1) ++log; return log; } // Attempts to use insertion sort on [begin, end). Will return false if more than // partial_insertion_sort_limit elements were moved, and abort sorting. Otherwise it will // successfully sort and return true. template<class Iter, class Compare> inline bool partial_insertion_sort(Iter begin, Iter end, Compare comp) { typedef typename boost::movelib::iterator_traits<Iter>::value_type T; typedef typename boost::movelib::iterator_traits<Iter>::size_type size_type; if (begin == end) return true; size_type limit = 0; for (Iter cur = begin + 1; cur != end; ++cur) { if (limit > partial_insertion_sort_limit) return false; Iter sift = cur; Iter sift_1 = cur - 1; // Compare first so we can avoid 2 moves for an element already positioned correctly. if (comp(*sift, *sift_1)) { T tmp = boost::move(*sift); do { *sift-- = boost::move(*sift_1); } while (sift != begin && comp(tmp, *--sift_1)); *sift = boost::move(tmp); limit += size_type(cur - sift); } } return true; } template<class Iter, class Compare> inline void sort2(Iter a, Iter b, Compare comp) { if (comp(*b, *a)) boost::adl_move_iter_swap(a, b); } // Sorts the elements *a, *b and *c using comparison function comp. template<class Iter, class Compare> inline void sort3(Iter a, Iter b, Iter c, Compare comp) { sort2(a, b, comp); sort2(b, c, comp); sort2(a, b, comp); } // Partitions [begin, end) around pivot *begin using comparison function comp. Elements equal // to the pivot are put in the right-hand partition. Returns the position of the pivot after // partitioning and whether the passed sequence already was correctly partitioned. Assumes the // pivot is a median of at least 3 elements and that [begin, end) is at least // insertion_sort_threshold long. template<class Iter, class Compare> pdqsort_detail::pair<Iter, bool> partition_right(Iter begin, Iter end, Compare comp) { typedef typename boost::movelib::iterator_traits<Iter>::value_type T; // Move pivot into local for speed. T pivot(boost::move(*begin)); Iter first = begin; Iter last = end; // Find the first element greater than or equal than the pivot (the median of 3 guarantees // this exists). while (comp(*++first, pivot)); // Find the first element strictly smaller than the pivot. We have to guard this search if // there was no element before *first. if (first - 1 == begin) while (first < last && !comp(*--last, pivot)); else while ( !comp(*--last, pivot)); // If the first pair of elements that should be swapped to partition are the same element, // the passed in sequence already was correctly partitioned. bool already_partitioned = first >= last; // Keep swapping pairs of elements that are on the wrong side of the pivot. Previously // swapped pairs guard the searches, which is why the first iteration is special-cased // above. while (first < last) { boost::adl_move_iter_swap(first, last); while (comp(*++first, pivot)); while (!comp(*--last, pivot)); } // Put the pivot in the right place. Iter pivot_pos = first - 1; *begin = boost::move(*pivot_pos); *pivot_pos = boost::move(pivot); return pdqsort_detail::pair<Iter, bool>(pivot_pos, already_partitioned); } // Similar function to the one above, except elements equal to the pivot are put to the left of // the pivot and it doesn't check or return if the passed sequence already was partitioned. // Since this is rarely used (the many equal case), and in that case pdqsort already has O(n) // performance, no block quicksort is applied here for simplicity. template<class Iter, class Compare> inline Iter partition_left(Iter begin, Iter end, Compare comp) { typedef typename boost::movelib::iterator_traits<Iter>::value_type T; T pivot(boost::move(*begin)); Iter first = begin; Iter last = end; while (comp(pivot, *--last)); if (last + 1 == end) while (first < last && !comp(pivot, *++first)); else while ( !comp(pivot, *++first)); while (first < last) { boost::adl_move_iter_swap(first, last); while (comp(pivot, *--last)); while (!comp(pivot, *++first)); } Iter pivot_pos = last; *begin = boost::move(*pivot_pos); *pivot_pos = boost::move(pivot); return pivot_pos; } template<class Iter, class Compare> void pdqsort_loop( Iter begin, Iter end, Compare comp , typename boost::movelib::iterator_traits<Iter>::size_type bad_allowed , bool leftmost = true) { typedef typename boost::movelib::iterator_traits<Iter>::size_type size_type; // Use a while loop for tail recursion elimination. while (true) { size_type size = size_type(end - begin); // Insertion sort is faster for small arrays. if (size < insertion_sort_threshold) { insertion_sort(begin, end, comp); return; } // Choose pivot as median of 3 or pseudomedian of 9. size_type s2 = size / 2; if (size > ninther_threshold) { sort3(begin, begin + s2, end - 1, comp); sort3(begin + 1, begin + (s2 - 1), end - 2, comp); sort3(begin + 2, begin + (s2 + 1), end - 3, comp); sort3(begin + (s2 - 1), begin + s2, begin + (s2 + 1), comp); boost::adl_move_iter_swap(begin, begin + s2); } else sort3(begin + s2, begin, end - 1, comp); // If *(begin - 1) is the end of the right partition of a previous partition operation // there is no element in [begin, end) that is smaller than *(begin - 1). Then if our // pivot compares equal to *(begin - 1) we change strategy, putting equal elements in // the left partition, greater elements in the right partition. We do not have to // recurse on the left partition, since it's sorted (all equal). if (!leftmost && !comp(*(begin - 1), *begin)) { begin = partition_left(begin, end, comp) + 1; continue; } // Partition and get results. pdqsort_detail::pair<Iter, bool> part_result = partition_right(begin, end, comp); Iter pivot_pos = part_result.first; bool already_partitioned = part_result.second; // Check for a highly unbalanced partition. size_type l_size = size_type(pivot_pos - begin); size_type r_size = size_type(end - (pivot_pos + 1)); bool highly_unbalanced = l_size < size / 8 || r_size < size / 8; // If we got a highly unbalanced partition we shuffle elements to break many patterns. if (highly_unbalanced) { // If we had too many bad partitions, switch to heapsort to guarantee O(n log n). if (--bad_allowed == 0) { boost::movelib::heap_sort(begin, end, comp); return; } if (l_size >= insertion_sort_threshold) { boost::adl_move_iter_swap(begin, begin + l_size / 4); boost::adl_move_iter_swap(pivot_pos - 1, pivot_pos - l_size / 4); if (l_size > ninther_threshold) { boost::adl_move_iter_swap(begin + 1, begin + (l_size / 4 + 1)); boost::adl_move_iter_swap(begin + 2, begin + (l_size / 4 + 2)); boost::adl_move_iter_swap(pivot_pos - 2, pivot_pos - (l_size / 4 + 1)); boost::adl_move_iter_swap(pivot_pos - 3, pivot_pos - (l_size / 4 + 2)); } } if (r_size >= insertion_sort_threshold) { boost::adl_move_iter_swap(pivot_pos + 1, pivot_pos + (1 + r_size / 4)); boost::adl_move_iter_swap(end - 1, end - r_size / 4); if (r_size > ninther_threshold) { boost::adl_move_iter_swap(pivot_pos + 2, pivot_pos + (2 + r_size / 4)); boost::adl_move_iter_swap(pivot_pos + 3, pivot_pos + (3 + r_size / 4)); boost::adl_move_iter_swap(end - 2, end - (1 + r_size / 4)); boost::adl_move_iter_swap(end - 3, end - (2 + r_size / 4)); } } } else { // If we were decently balanced and we tried to sort an already partitioned // sequence try to use insertion sort. if (already_partitioned && partial_insertion_sort(begin, pivot_pos, comp) && partial_insertion_sort(pivot_pos + 1, end, comp)) return; } // Sort the left partition first using recursion and do tail recursion elimination for // the right-hand partition. pdqsort_loop<Iter, Compare>(begin, pivot_pos, comp, bad_allowed, leftmost); begin = pivot_pos + 1; leftmost = false; } } } template<class Iter, class Compare> void pdqsort(Iter begin, Iter end, Compare comp) { if (begin == end) return; typedef typename boost::movelib::iterator_traits<Iter>::size_type size_type; pdqsort_detail::pdqsort_loop<Iter, Compare>(begin, end, comp, pdqsort_detail::log2(size_type(end - begin))); } } //namespace movelib { } //namespace boost { #include <boost/move/detail/config_end.hpp> #endif //BOOST_MOVE_ALGO_PDQSORT_HPP