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
|
// Copyright (C) 2003 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#ifndef DLIB_QUEUE_SORt_1_
#define DLIB_QUEUE_SORt_1_
#include "queue_sort_abstract.h"
#include "../algs.h"
#include <vector>
#include "../sort.h"
namespace dlib
{
template <
typename queue_base
>
class queue_sort_1 : public queue_base
{
typedef typename queue_base::type T;
public:
/*!
This implementation uses the QuickSort algorithm and
when the quicksort depth goes too high it uses the dlib::qsort_array()
function on the data.
!*/
void sort (
);
template <typename compare_type>
void sort (
const compare_type& compare
)
{
if (this->size() > 1)
{
sort_this_queue(*this,0,compare);
}
}
private:
template <typename compare_type>
void sort_this_queue (
queue_base& queue,
long depth,
const compare_type& compare
)
/*!
ensures
each element in the queue is < the element behind it according
to compare
!*/
{
if (queue.size() <= 1)
{
// already sorted
}
else if (queue.size() <= 29)
{
T vect[29];
const unsigned long size = queue.size();
for (unsigned long i = 0; i < size; ++i)
{
queue.dequeue(vect[i]);
}
isort_array(vect,0,size-1,compare);
for (unsigned long i = 0; i < size; ++i)
{
queue.enqueue(vect[i]);
}
}
else if (depth > 50)
{
std::vector<T> vect(queue.size());
for (unsigned long i = 0; i < vect.size(); ++i)
{
queue.dequeue(vect[i]);
}
hsort_array(vect,0,vect.size()-1,compare);
for (unsigned long i = 0; i < vect.size(); ++i)
{
queue.enqueue(vect[i]);
}
}
else
{
queue_base left, right;
T partition_element;
T temp;
// do this just to avoid a compiler warning
assign_zero_if_built_in_scalar_type(temp);
assign_zero_if_built_in_scalar_type(partition_element);
queue.dequeue(partition_element);
// partition queue into left and right
while (queue.size() > 0)
{
queue.dequeue(temp);
if (compare(temp , partition_element))
{
left.enqueue(temp);
}
else
{
right.enqueue(temp);
}
}
long ratio;
if (left.size() > right.size())
ratio = left.size()/(right.size()+1); // add 1 so we can't divide by zero
else
ratio = right.size()/(left.size()+1);
sort_this_queue(left,ratio+depth,compare);
sort_this_queue(right,ratio+depth,compare);
// combine the two queues
left.swap(queue);
queue.enqueue(partition_element);
queue.cat(right);
}
}
};
template <
typename queue_base
>
inline void swap (
queue_sort_1<queue_base>& a,
queue_sort_1<queue_base>& b
) { a.swap(b); }
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
// member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
template <
typename queue_base
>
void queue_sort_1<queue_base>::
sort (
)
{
if (this->size() > 1)
{
sort_this_queue(*this,0,std::less<typename queue_base::type>());
}
}
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_QUEUE_SORt_1_
|
