123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215 |
- //----------------------------------------------------------------------------
- /// @file heap_sort.hpp
- /// @brief Insertion Sort algorithm
- ///
- /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
- /// Distributed under the Boost Software License, Version 1.0.\n
- /// ( See accompanying file LICENSE_1_0.txt or copy at
- /// http://www.boost.org/LICENSE_1_0.txt )
- /// @version 0.1
- ///
- /// @remarks
- //-----------------------------------------------------------------------------
- #ifndef __BOOST_SORT_INTROSORT_DETAIL_HEAP_SORT_HPP
- #define __BOOST_SORT_INTROSORT_DETAIL_HEAP_SORT_HPP
- #include <cassert>
- #include <cstdint>
- #include <iterator>
- #include <stdexcept>
- #include <utility> // for std::swap
- #include <boost/sort/common/util/traits.hpp>
- namespace boost
- {
- namespace sort
- {
- namespace heap_detail
- {
- namespace bscu = boost::sort::common::util;
- //
- //---------------------------------------------------------------------------
- // struct : heap_sort
- /// @brief : Heap sort algorithm
- /// @remarks This algorithm is O(NLogN)
- //---------------------------------------------------------------------------
- template < class Iter_t, class Compare >
- struct heap_sort
- {
- typedef bscu::value_iter<Iter_t> value_t;
- //
- //------------------------------------------------------------------------
- // function : sort3
- /// @brief Sort and signal the changes of three values
- /// @param val_0 : first value to compare
- /// @param val_1 : second value to compare
- /// @param val_2 : third value to compare
- /// @param [out] bool_0 : if true indicates val_0 had been changed
- /// @param [out] bool_1 : if true indicates val_1 had been changed
- /// @param [out] bool_2 : if true indicates val_2 had been changed
- /// @return if true , some value had changed
- /// @remarks
- //------------------------------------------------------------------------
- bool sort3 (value_t &val_0, value_t &val_1, value_t &val_2, bool &bool_0,
- bool &bool_1, bool &bool_2)
- {
- bool_0 = bool_1 = bool_2 = false;
- int value = 0;
- if (val_0 < val_1) value += 4;
- if (val_1 < val_2) value += 2;
- if (val_0 < val_2) value += 1;
- switch (value)
- {
- case 0: break;
- case 2:
- std::swap (val_1, val_2);
- bool_1 = bool_2 = true;
- break;
- case 3:
- if (not(val_0 > val_1)) {
- std::swap (val_0, val_2);
- bool_0 = bool_2 = true;
- }
- else
- {
- auto aux = std::move (val_2);
- val_2 = std::move (val_1);
- val_1 = std::move (val_0);
- val_0 = std::move (aux);
- bool_0 = bool_1 = bool_2 = true;
- };
- break;
- case 4:
- std::swap (val_0, val_1);
- bool_0 = bool_1 = true;
- break;
- case 5:
- if (val_1 > val_2) {
- auto aux = std::move (val_0);
- val_0 = std::move (val_1);
- val_1 = std::move (val_2);
- val_2 = std::move (aux);
- bool_0 = bool_1 = bool_2 = true;
- }
- else
- {
- std::swap (val_0, val_2);
- bool_0 = bool_2 = true;
- };
- break;
- case 7:
- std::swap (val_0, val_2);
- bool_0 = bool_2 = true;
- break;
- default: abort ( );
- };
- return (bool_0 or bool_1 or bool_2);
- };
- //
- //-----------------------------------------------------------------------
- // function : make_heap
- /// @brief Make the heap for to extract the sorted elements
- /// @param first : iterator to the first element of the range
- /// @param nelem : number of lements of the range
- /// @param comp : object for to compare two elements
- /// @remarks This algorithm is O(NLogN)
- //------------------------------------------------------------------------
- void make_heap (Iter_t first, size_t nelem, Compare comp)
- {
- size_t pos_father, pos_son;
- Iter_t iter_father = first, iter_son = first;
- bool sw = false;
- for (size_t i = 1; i < nelem; ++i)
- {
- pos_father = i;
- iter_father = first + i;
- sw = false;
- do
- {
- iter_son = iter_father;
- pos_son = pos_father;
- pos_father = (pos_son - 1) >> 1;
- iter_father = first + pos_father;
- if ((sw = comp (*iter_father, *iter_son)))
- std::swap (*iter_father, *iter_son);
- } while (sw and pos_father != 0);
- };
- };
- //
- //------------------------------------------------------------------------
- // function : heap_sort
- /// @brief : Heap sort algorithm
- /// @param first: iterator to the first element of the range
- /// @param last : iterator to the next element of the last in the range
- /// @param comp : object for to do the comparison between the elements
- /// @remarks This algorithm is O(NLogN)
- //------------------------------------------------------------------------
- heap_sort (Iter_t first, Iter_t last, Compare comp)
- {
- assert ((last - first) >= 0);
- size_t nelem = last - first;
- if (nelem < 2) return;
- //--------------------------------------------------------------------
- // Creating the initial heap
- //--------------------------------------------------------------------
- make_heap (first, nelem, comp);
- //--------------------------------------------------------------------
- // Sort the heap
- //--------------------------------------------------------------------
- size_t pos_father, pos_son;
- Iter_t iter_father = first, iter_son = first;
- bool sw = false;
- for (size_t i = 1; i < nelem; ++i)
- {
- std::swap (*first, *(first + (nelem - i)));
- pos_father = 0;
- pos_son = 1;
- iter_father = first;
- sw = true;
- while (sw and pos_son < (nelem - i))
- {
- // if the father have two sons must select the bigger
- iter_son = first + pos_son;
- if ((pos_son + 1) < (nelem - i) and
- comp (*iter_son, *(iter_son + 1)))
- {
- ++pos_son;
- ++iter_son;
- };
- if ((sw = comp (*iter_father, *iter_son)))
- std::swap (*iter_father, *iter_son);
- pos_father = pos_son;
- iter_father = iter_son;
- pos_son = (pos_father << 1) + 1;
- };
- };
- };
- }; // End class heap_sort
- }; // end namespace heap_sort
- namespace bscu = boost::sort::common::util;
- template < class Iter_t, typename Compare = bscu::compare_iter < Iter_t > >
- void heap_sort (Iter_t first, Iter_t last, Compare comp = Compare())
- {
- heap_detail::heap_sort<Iter_t, Compare> ( first, last, comp);
- }
- //
- //****************************************************************************
- }; // End namespace sort
- }; // End namespace boost
- //****************************************************************************
- //
- #endif
|