1 //----------------------------------------------------------------------------
2 /// @file insert_sort.hpp
3 /// @brief Insertion Sort algorithm
4 ///
5 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
6 /// Distributed under the Boost Software License, Version 1.0.\n
7 /// ( See accompanying file LICENSE_1_0.txt or copy at
8 /// http://www.boost.org/LICENSE_1_0.txt )
9 /// @version 0.1
10 ///
11 /// @remarks
12 //-----------------------------------------------------------------------------
13 #ifndef __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
14 #define __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
15
16 #include <functional>
17 #include <iterator>
18 #include <algorithm>
19 #include <utility> // std::swap
20 #include <boost/sort/common/util/traits.hpp>
21 #include <boost/sort/common/util/insert.hpp>
22
23 namespace boost
24 {
25 namespace sort
26 {
27 using common::util::compare_iter;
28 using common::util::value_iter;
29 //
30 //-----------------------------------------------------------------------------
31 // function : insert_sort
32 /// @brief : Insertion sort algorithm
33 /// @param first: iterator to the first element of the range
34 /// @param last : iterator to the next element of the last in the range
35 /// @param comp : object for to do the comparison between the elements
36 /// @remarks This algorithm is O(N^2)
37 //-----------------------------------------------------------------------------
38 template < class Iter_t, typename Compare = compare_iter < Iter_t > >
insert_sort(Iter_t first,Iter_t last,Compare comp=Compare ())39 static void insert_sort (Iter_t first, Iter_t last,
40 Compare comp = Compare())
41 {
42 //--------------------------------------------------------------------
43 // DEFINITIONS
44 //--------------------------------------------------------------------
45 typedef value_iter< Iter_t > value_t;
46
47 if ((last - first) < 2) return;
48
49 for (Iter_t it_examine = first + 1; it_examine != last; ++it_examine)
50 {
51 value_t Aux = std::move (*it_examine);
52 Iter_t it_insertion = it_examine;
53
54 while (it_insertion != first and comp (Aux, *(it_insertion - 1)))
55 {
56 *it_insertion = std::move (*(it_insertion - 1));
57 --it_insertion;
58 };
59 *it_insertion = std::move (Aux);
60 };
61 };
62
63 /*
64 //
65 //-----------------------------------------------------------------------------
66 // function : insert_partial_sort
67 /// @brief : Insertion sort of elements sorted
68 /// @param first: iterator to the first element of the range
69 /// @param mid : last pointer of the sorted data, and first pointer to the
70 /// elements to insert
71 /// @param last : iterator to the next element of the last in the range
72 /// @param comp : object for to do the comparison between the elements
73 /// @remarks This algorithm is O(N^2)
74 //-----------------------------------------------------------------------------
75 template < class Iter_t, typename Compare = compare_iter < Iter_t > >
76 void insert_partial_sort (Iter_t first, Iter_t mid, Iter_t last,
77 Compare comp = Compare())
78 {
79 //--------------------------------------------------------------------
80 // DEFINITIONS
81 //--------------------------------------------------------------------
82 typedef value_iter< Iter_t > value_t;
83
84 if ( mid == last ) return ;
85 insert_sort ( mid, last, comp);
86 if (first == mid) return ;
87
88 // creation of the vector of elements to insert and their position in the
89 // sorted part
90 std::vector<Iter_t> viter ;
91 std::vector<value_t> vdata ;
92
93 for ( Iter_t alpha = mid ; alpha != last ; ++alpha)
94 vdata.push_back ( std::move ( *alpha));
95
96 Iter_t linf = first , lsup = mid ;
97 for ( uint32_t i= 0 ; i < vdata.size() ; ++i)
98 { Iter_t it1 = std::upper_bound ( linf, lsup , vdata[i], comp);
99 viter.push_back ( it1 );
100 linf = it1 ;
101 };
102
103 // moving the elements
104 viter.push_back ( mid) ;
105 for ( uint32_t i = viter.size() -1 ; i!= 0 ; --i)
106 { Iter_t src = viter[i], limit = viter[i-1];
107 Iter_t dest = src + ( i);
108 while ( src != limit) * (--dest) = std::move ( *(--src));
109 *(viter[i-1] + (i -1)) = std::move (vdata[i-1]);
110 };
111 }
112 */
113 //
114 //****************************************************************************
115 }; // End namespace sort
116 }; // End namespace boost
117 //****************************************************************************
118 //
119 #endif
120