Server : Apache/2.4.41 (Ubuntu) System : Linux absol.cf 5.4.0-198-generic #218-Ubuntu SMP Fri Sep 27 20:18:53 UTC 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.33 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, Directory :  /usr/include/boost/sort/insert_sort/

Upload File : current_dir [ Writeable ] document_root [ Writeable ]

//----------------------------------------------------------------------------
/// @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