1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
28 // FIXME: The comparison functions are non-standard (they take an extra void * for user data, which is both good and bad).
29 // Also, most of the sorts here are kinda useless in practice (either use vogl_introsort.h or vogl_mergesort.h), except maybe the index sorts.
32 #include "vogl_core.h"
33 #include "vogl_rand.h"
38 inline bool default_compare_func(const T &lhs, const T &rhs, const void *pData)
40 VOGL_NOTE_UNUSED(pData);
44 template <typename T, typename F>
45 inline void insertion_sort(int size, T *a, F compare_func, void *pCompare_func_data = NULL)
47 for (int i = 1; i < size; i++)
52 while ((j >= 0) && (compare_func(value, a[j], pCompare_func_data)))
63 inline void insertion_sort(int size, T *a)
65 insertion_sort(size, a, default_compare_func<T>, NULL);
68 template <typename T, typename F>
69 inline void shell_sort(int size, T *a, F compare_func, void *pCompare_func_data = NULL)
71 static const uint sequence[] = { 1, 4, 10, 23, 57, 132, 301, 701, 1577, 3548 };
72 const uint cSequenceSize = sizeof(sequence) / sizeof(sequence[0]);
74 int s = cSequenceSize - 1;
78 int increment = sequence[s];
80 for (int i = increment; i < size; i++)
85 while ((j >= increment) && (compare_func(temp, a[j - increment], pCompare_func_data)))
87 a[j] = a[j - increment];
98 inline void shell_sort(int size, T *a)
100 shell_sort(size, a, default_compare_func<T>, NULL);
103 template <typename T, typename F>
104 inline void heap_sort(int size, T *a, F compare_func, void *pCompare_func_data = NULL)
106 int start = (size - 2) >> 1;
113 int child = (root << 1) + 1;
117 if (((child + 1) < size) && (compare_func(a[child], a[child + 1], pCompare_func_data)))
120 if (compare_func(a[root], a[child], pCompare_func_data))
122 utils::swap(a[root], a[child]);
135 utils::swap(a[end], a[0]);
141 int child = (root << 1) + 1;
145 if (((child + 1) < end) && (compare_func(a[child], a[child + 1], pCompare_func_data)))
148 if (compare_func(a[root], a[child], pCompare_func_data))
150 utils::swap(a[root], a[child]);
161 template <typename T>
162 inline void heap_sort(int size, T *a)
164 heap_sort(size, a, default_compare_func<T>, NULL);
167 template <typename T, typename F>
168 inline void indexed_heap_sort(int size, const T *a, uint *pIndices, F compare_func, void *pCompare_func_data = NULL)
170 int start = (size - 2) >> 1;
177 int child = (root << 1) + 1;
181 if (((child + 1) < size) && (compare_func(a[pIndices[child]], a[pIndices[child + 1]], pCompare_func_data)))
184 if (compare_func(a[pIndices[root]], a[pIndices[child]], pCompare_func_data))
186 utils::swap(pIndices[root], pIndices[child]);
199 utils::swap(pIndices[end], pIndices[0]);
205 int child = (root << 1) + 1;
209 if (((child + 1) < end) && (compare_func(a[pIndices[child]], a[pIndices[child + 1]], pCompare_func_data)))
212 if (compare_func(a[pIndices[root]], a[pIndices[child]], pCompare_func_data))
214 utils::swap(pIndices[root], pIndices[child]);
225 template <typename T>
226 inline void indexed_heap_sort(int size, const T *a, uint *pIndices)
228 indexed_heap_sort(size, a, pIndices, default_compare_func<T>, NULL);
231 inline bool sort_test()
233 uint num_failures = 0;
237 for (uint trial = 0; trial < 50000; trial++)
239 uint sz = r.irand_inclusive(1, 8192);
240 uint z = r.irand_inclusive(2, 8192);
243 vogl::vector<uint> x(sz);
244 for (uint i = 0; i < x.size(); i++)
245 x[i] = r.irand(0, z);
247 vogl::vector<uint> indices(sz);
248 for (uint i = 0; i < sz; i++)
251 bool used_indices = false;
253 switch (r.irand_inclusive(0, 3))
256 vogl::insertion_sort(x.size(), x.get_ptr());
259 vogl::shell_sort(x.size(), x.get_ptr());
262 vogl::heap_sort(x.size(), x.get_ptr());
265 vogl::indexed_heap_sort(x.size(), x.get_ptr(), indices.get_ptr());
272 for (uint i = 1; i < x.size(); i++)
274 if (x[indices[i - 1]] > x[indices[i]])
283 for (uint i = 1; i < x.size(); i++)
294 return num_failures == 0;