summaryrefslogtreecommitdiff
path: root/boost/sort/heap_sort/heap_sort.hpp
blob: 9e89d00b8ccb42cc015462e454ba89881d43c4b7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
//----------------------------------------------------------------------------
/// @file heap_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_HEAP_SORT_HPP
#define __BOOST_SORT_INTROSORT_DETAIL_HEAP_SORT_HPP

#include <cassert>
#include <cstdint>
#include <iterator>
#include <stdexcept>
#include <utility> // for std::swap
#include <boost/sort/common/util/traits.hpp>

namespace boost
{
namespace sort
{
namespace heap_detail
{
namespace bscu = boost::sort::common::util;
//
//---------------------------------------------------------------------------
//  struct : heap_sort
/// @brief : Heap sort algorithm
/// @remarks This algorithm is O(NLogN)
//---------------------------------------------------------------------------
template < class Iter_t, class Compare >
struct heap_sort
{
    typedef bscu::value_iter<Iter_t> value_t;

    //
    //------------------------------------------------------------------------
    //  function : sort3
    /// @brief Sort and signal the changes of three values
    /// @param val_0 : first value to compare
    /// @param val_1 : second value to compare
    /// @param val_2 : third value to compare
    /// @param [out] bool_0 : if true indicates val_0 had been changed
    /// @param [out] bool_1 : if true indicates val_1 had been changed
    /// @param [out] bool_2 : if true indicates val_2 had been changed
    /// @return if true , some value had changed
    /// @remarks
    //------------------------------------------------------------------------
    bool sort3 (value_t &val_0, value_t &val_1, value_t &val_2, bool &bool_0,
                bool &bool_1, bool &bool_2)
    {
        bool_0 = bool_1 = bool_2 = false;
        int value = 0;
        if (val_0 < val_1) value += 4;
        if (val_1 < val_2) value += 2;
        if (val_0 < val_2) value += 1;

        switch (value)
        {
            case 0: break;

            case 2:
                std::swap (val_1, val_2);
                bool_1 = bool_2 = true;
                break;

            case 3:
                if (not(val_0 > val_1)) {
                    std::swap (val_0, val_2);
                    bool_0 = bool_2 = true;
                }
                else
                {
                    auto aux = std::move (val_2);
                    val_2 = std::move (val_1);
                    val_1 = std::move (val_0);
                    val_0 = std::move (aux);
                    bool_0 = bool_1 = bool_2 = true;
                };
                break;

            case 4:
                std::swap (val_0, val_1);
                bool_0 = bool_1 = true;
                break;

            case 5:
                if (val_1 > val_2) {
                    auto aux = std::move (val_0);
                    val_0 = std::move (val_1);
                    val_1 = std::move (val_2);
                    val_2 = std::move (aux);
                    bool_0 = bool_1 = bool_2 = true;
                }
                else
                {
                    std::swap (val_0, val_2);
                    bool_0 = bool_2 = true;
                };
                break;

            case 7:
                std::swap (val_0, val_2);
                bool_0 = bool_2 = true;
                break;

            default: abort ( );
        };
        return (bool_0 or bool_1 or bool_2);
    };
    //
    //-----------------------------------------------------------------------
    //  function : make_heap
    /// @brief Make the heap for to extract the sorted elements
    /// @param first : iterator to the first element of the range
    /// @param nelem : number of lements of the range
    /// @param comp : object for to compare two elements
    /// @remarks This algorithm is O(NLogN)
    //------------------------------------------------------------------------
    void make_heap (Iter_t first, size_t nelem, Compare comp)
    {
        size_t pos_father, pos_son;
        Iter_t iter_father = first, iter_son = first;
        bool sw = false;

        for (size_t i = 1; i < nelem; ++i)
        {
            pos_father = i;
            iter_father = first + i;
            sw = false;
            do
            {
                iter_son = iter_father;
                pos_son = pos_father;
                pos_father = (pos_son - 1) >> 1;
                iter_father = first + pos_father;
                if ((sw = comp (*iter_father, *iter_son)))
                    std::swap (*iter_father, *iter_son);
            } while (sw and pos_father != 0);
        };
    };
    //
    //------------------------------------------------------------------------
    //  function : heap_sort
    /// @brief : Heap 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(NLogN)
    //------------------------------------------------------------------------
    heap_sort (Iter_t first, Iter_t last, Compare comp)
    {
        assert ((last - first) >= 0);
        size_t nelem = last - first;
        if (nelem < 2) return;

        //--------------------------------------------------------------------
        // Creating the initial heap
        //--------------------------------------------------------------------
        make_heap (first, nelem, comp);

        //--------------------------------------------------------------------
        //  Sort the heap
        //--------------------------------------------------------------------
        size_t pos_father, pos_son;
        Iter_t iter_father = first, iter_son = first;

        bool sw = false;
        for (size_t i = 1; i < nelem; ++i)
        {
            std::swap (*first, *(first + (nelem - i)));
            pos_father = 0;
            pos_son = 1;
            iter_father = first;
            sw = true;
            while (sw and pos_son < (nelem - i))
            {
                // if the father have two sons must select the bigger
                iter_son = first + pos_son;
                if ((pos_son + 1) < (nelem - i) and
                    comp (*iter_son, *(iter_son + 1)))
                {
                    ++pos_son;
                    ++iter_son;
                };
                if ((sw = comp (*iter_father, *iter_son)))
                    std::swap (*iter_father, *iter_son);
                pos_father = pos_son;
                iter_father = iter_son;
                pos_son = (pos_father << 1) + 1;
            };
        };
    };
}; // End class heap_sort
}; // end namespace heap_sort

namespace bscu = boost::sort::common::util;

template < class Iter_t, typename Compare = bscu::compare_iter < Iter_t > >
void heap_sort (Iter_t first, Iter_t last, Compare comp = Compare())
{
	heap_detail::heap_sort<Iter_t, Compare> ( first, last, comp);
}
//
//****************************************************************************
}; //    End namespace sort
}; //    End namespace boost
//****************************************************************************
//
#endif