| 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 <ciso646> |
|---|
| 17 | #include <functional> |
|---|
| 18 | #include <iterator> |
|---|
| 19 | #include <algorithm> |
|---|
| 20 | #include <utility> // std::swap |
|---|
| 21 | #include <boost/sort/common/util/traits.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 > > |
|---|
| 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 | }; // End namespace sort |
|---|
| 66 | }; // End namespace boost |
|---|
| 67 | //**************************************************************************** |
|---|
| 68 | // |
|---|
| 69 | #endif |
|---|
| 70 | |
|---|
