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 <ciso646>
0017 #include <functional>
0018 #include <iterator>
0019 #include <algorithm>
0020 #include <utility> // std::swap
0021 #include <boost/sort/common/util/traits.hpp>
0022
0023 namespace boost
0024 {
0025 namespace sort
0026 {
0027 using common::util::compare_iter;
0028 using common::util::value_iter;
0029 //
0030 //-----------------------------------------------------------------------------
0031 //  function : insert_sort
0032 /// @brief : Insertion sort algorithm
0033 /// @param first: iterator to the first element of the range
0034 /// @param last : iterator to the next element of the last in the range
0035 /// @param comp : object for to do the comparison between the elements
0036 /// @remarks This algorithm is O(N^2)
0037 //-----------------------------------------------------------------------------
0038 template < class Iter_t, typename Compare = compare_iter < Iter_t > >
0039 static void insert_sort (Iter_t first, Iter_t last,
0040                          Compare comp = Compare())
0041 {
0042     //--------------------------------------------------------------------
0043     //                   DEFINITIONS
0044     //--------------------------------------------------------------------
0045     typedef value_iter< Iter_t > value_t;
0046
0047     if ((last - first) < 2) return;
0048
0049     for (Iter_t it_examine = first + 1; it_examine != last; ++it_examine)
0050     {
0051         value_t Aux = std::move (*it_examine);
0052         Iter_t it_insertion = it_examine;
0053
0054         while (it_insertion != first and comp (Aux, *(it_insertion - 1)))
0055         {
0056             *it_insertion = std::move (*(it_insertion - 1));
0057             --it_insertion;
0058         };
0059         *it_insertion = std::move (Aux);
0060     };
0061 };
0062
0063 //
0064 //****************************************************************************
0065 }; //    End namespace sort
0066 }; //    End namespace boost
0067 //****************************************************************************
0068 //
0069 #endif