sort/insert_sort/insert_sort.hpp

0001 //----------------------------------------------------------------------------
0002 /// @file insert_sort.hpp
0003 /// @brief Insertion Sort algorithm
0004 ///
0005 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
0006 ///         Distributed under the Boost Software License, Version 1.0.\n
0007 ///         ( See accompanying file LICENSE_1_0.txt or copy at
0008 ///           http://www.boost.org/LICENSE_1_0.txt  )
0009 /// @version 0.1
0010 ///
0011 /// @remarks
0012 //-----------------------------------------------------------------------------
0013 #ifndef __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
0014 #define __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
0015
0016 #include <functional>
0017 #include <iterator>
0018 #include <algorithm>
0019 #include <utility> // std::swap
0020 #include <boost/sort/common/util/traits.hpp>
0021
0022 namespace boost
0023 {
0024 namespace sort
0025 {
0026 using common::util::compare_iter;
0027 using common::util::value_iter;
0028 //
0029 //-----------------------------------------------------------------------------
0030 //  function : insert_sort
0031 /// @brief : Insertion sort algorithm
0032 /// @param first: iterator to the first element of the range
0033 /// @param last : iterator to the next element of the last in the range
0034 /// @param comp : object for to do the comparison between the elements
0035 /// @remarks This algorithm is O(N^2)
0036 //-----------------------------------------------------------------------------
0037 template < class Iter_t, typename Compare = compare_iter < Iter_t > >
0038 static void insert_sort (Iter_t first, Iter_t last,
0039                          Compare comp = Compare())
0040 {
0041     //--------------------------------------------------------------------
0042     //                   DEFINITIONS
0043     //--------------------------------------------------------------------
0044     typedef value_iter< Iter_t > value_t;
0045
0046     if ((last - first) < 2) return;
0047
0048     for (Iter_t it_examine = first + 1; it_examine != last; ++it_examine)
0049     {
0050         value_t Aux = std::move (*it_examine);
0051         Iter_t it_insertion = it_examine;
0052
0053         while (it_insertion != first && comp (Aux, *(it_insertion - 1)))
0054         {
0055             *it_insertion = std::move (*(it_insertion - 1));
0056             --it_insertion;
0057         };
0058         *it_insertion = std::move (Aux);
0059     };
0060 }
0061
0062 //
0063 //****************************************************************************
0064 } //    End namespace sort
0065 } //    End namespace boost
0066 //****************************************************************************
0067 //
0068 #endif