123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119 |
- //----------------------------------------------------------------------------
- /// @file insert_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_INSERT_SORT_HPP
- #define __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
- #include <functional>
- #include <iterator>
- #include <algorithm>
- #include <utility> // std::swap
- #include <boost/sort/common/util/traits.hpp>
- #include <boost/sort/common/util/insert.hpp>
- namespace boost
- {
- namespace sort
- {
- using common::util::compare_iter;
- using common::util::value_iter;
- //
- //-----------------------------------------------------------------------------
- // function : insert_sort
- /// @brief : Insertion 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(N^2)
- //-----------------------------------------------------------------------------
- template < class Iter_t, typename Compare = compare_iter < Iter_t > >
- static void insert_sort (Iter_t first, Iter_t last,
- Compare comp = Compare())
- {
- //--------------------------------------------------------------------
- // DEFINITIONS
- //--------------------------------------------------------------------
- typedef value_iter< Iter_t > value_t;
- if ((last - first) < 2) return;
- for (Iter_t it_examine = first + 1; it_examine != last; ++it_examine)
- {
- value_t Aux = std::move (*it_examine);
- Iter_t it_insertion = it_examine;
- while (it_insertion != first and comp (Aux, *(it_insertion - 1)))
- {
- *it_insertion = std::move (*(it_insertion - 1));
- --it_insertion;
- };
- *it_insertion = std::move (Aux);
- };
- };
- /*
- //
- //-----------------------------------------------------------------------------
- // function : insert_partial_sort
- /// @brief : Insertion sort of elements sorted
- /// @param first: iterator to the first element of the range
- /// @param mid : last pointer of the sorted data, and first pointer to the
- /// elements to insert
- /// @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(N^2)
- //-----------------------------------------------------------------------------
- template < class Iter_t, typename Compare = compare_iter < Iter_t > >
- void insert_partial_sort (Iter_t first, Iter_t mid, Iter_t last,
- Compare comp = Compare())
- {
- //--------------------------------------------------------------------
- // DEFINITIONS
- //--------------------------------------------------------------------
- typedef value_iter< Iter_t > value_t;
- if ( mid == last ) return ;
- insert_sort ( mid, last, comp);
- if (first == mid) return ;
- // creation of the vector of elements to insert and their position in the
- // sorted part
- std::vector<Iter_t> viter ;
- std::vector<value_t> vdata ;
- for ( Iter_t alpha = mid ; alpha != last ; ++alpha)
- vdata.push_back ( std::move ( *alpha));
- Iter_t linf = first , lsup = mid ;
- for ( uint32_t i= 0 ; i < vdata.size() ; ++i)
- { Iter_t it1 = std::upper_bound ( linf, lsup , vdata[i], comp);
- viter.push_back ( it1 );
- linf = it1 ;
- };
- // moving the elements
- viter.push_back ( mid) ;
- for ( uint32_t i = viter.size() -1 ; i!= 0 ; --i)
- { Iter_t src = viter[i], limit = viter[i-1];
- Iter_t dest = src + ( i);
- while ( src != limit) * (--dest) = std::move ( *(--src));
- *(viter[i-1] + (i -1)) = std::move (vdata[i-1]);
- };
- }
- */
- //
- //****************************************************************************
- }; // End namespace sort
- }; // End namespace boost
- //****************************************************************************
- //
- #endif
|