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 **************************************************************************/
27 // File: vogl_introsort.cpp
28 #include "vogl_core.h"
29 #include "vogl_introsort.h"
30 #include "vogl_sort.h"
31 #include "vogl_mergesort.h"
32 #include "vogl_radix_sort.h"
36 struct sort_test_struct
40 bool operator<(const sort_test_struct &rhs) const
51 double std_sort_total_time = 0;
52 double introsort_total_time = 0;
53 double heapsort_total_time = 0;
54 double shellsort_total_time = 0;
55 double mergesort_total_time = 0;
56 double radixsort_total_time = 0;
58 double string_std_sort_total_time = 0;
59 double string_introsort_total_time = 0;
60 double string_mergesort_total_time = 0;
62 for (uint t = 0; t < 1000; t++)
64 uint n = g_random.irand_inclusive(0, 100000);
68 uint k = static_cast<uint>((1ULL << g_random.irand_inclusive(0, 31)) - 1UL);
69 for (uint i = 0; i < n; i++)
70 x[i] = g_random.irand_inclusive(0, k);
72 if (g_random.irand(0, 30) == 0)
75 if (g_random.get_bit())
79 printf("------------------------------\n");
80 printf("iter: %u, n: %u:\n", t, n);
84 vogl::timed_scope tm("introsort");
85 introsort(y.begin(), y.end());
86 introsort_total_time += tm.get_elapsed_secs();
93 vogl::timed_scope tm("std::sort");
94 std::sort(y.begin(), y.end());
95 std_sort_total_time += tm.get_elapsed_secs();
102 vogl::timed_scope tm("heap_sort");
103 heap_sort(y.size(), y.get_ptr());
104 heapsort_total_time += tm.get_elapsed_secs();
111 vogl::timed_scope tm("shell_sort");
112 shell_sort(y.size(), y.get_ptr());
113 shellsort_total_time += tm.get_elapsed_secs();
120 vogl::timed_scope tm("merge_sort");
122 mergesort_total_time += tm.get_elapsed_secs();
129 vogl::timed_scope tm("radix_sort");
131 vogl::vector<int> z(n);
132 int *pSorted = radix_sort(n, y.get_ptr(), z.get_ptr(), 0, sizeof(int));
134 for (uint i = 1; i < n; i++)
135 if (pSorted[i] < pSorted[i - 1])
138 radixsort_total_time += tm.get_elapsed_secs();
141 printf("%u, std::sort: %f introsort: %f, heapsort: %f, shellsort: %f, mergesort: %f, radixsort: %f\n", n, std_sort_total_time, introsort_total_time, heapsort_total_time, shellsort_total_time, mergesort_total_time, radixsort_total_time);
143 // mergesort stability test
144 // TODO: This doesn't below here
145 vogl::vector<sort_test_struct> xx(n);
146 for (uint i = 0; i < n; i++)
148 xx[i].i = x[i] & 0xFFFF;
154 for (uint i = 1; i < n; i++)
156 if (xx[i - 1].i > xx[i].i)
158 if (xx[i - 1].i == xx[i].i)
160 if (xx[i - 1].j >= xx[i].j)
166 dynamic_string_array sx(n);
167 for (uint i = 0; i < n; i++)
168 sx[i].format("%u", x[i]);
170 dynamic_string_array sy;
174 vogl::timed_scope tm("introsort string");
175 introsort(sy.begin(), sy.end());
176 string_introsort_total_time += tm.get_elapsed_secs();
183 vogl::timed_scope tm("std::sort string");
184 std::sort(sy.begin(), sy.end());
185 string_std_sort_total_time += tm.get_elapsed_secs();
192 vogl::timed_scope tm("merge_sort string");
194 string_mergesort_total_time += tm.get_elapsed_secs();
199 printf("%u, string std::sort: %f introsort: %f mergesort: %f\n", n, string_std_sort_total_time, string_introsort_total_time, string_mergesort_total_time);