Debian Codegraph @

packages/seacas/applications/nem_spread/sort_utils.C

raw
1 /*
2 * Copyright(C) 1999-2023 National Technology & Engineering Solutions
3 * of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with
4 * NTESS, the U.S. Government retains certain rights in this software.
5 *
6 * See packages/seacas/LICENSE for details
7 */
8
9 #define DEBUG_SORT 1
10 #if DEBUG_SORT
11 #include <cassert>
12 #include <cstdio>
13 #include <fmt/ostream.h>
14 #endif
15
16 #include <cstddef> // for size_t
17 #include <cstdint> // for int64_t
18
19 /*
20 * The following 'indexed qsort' routine is modified from Sedgewicks
21 * algorithm It selects the pivot based on the median of the left,
22 * right, and center values to try to avoid degenerate cases occurring
23 * when a single value is chosen. It performs a quicksort on
24 * intervals down to the GDS_QSORT_CUTOFF size and then performs a final
25 * insertion sort on the almost sorted final array. Based on data in
26 * Sedgewick, the GDS_QSORT_CUTOFF value should be between 5 and 20.
27 *
28 * See Sedgewick for further details
29 * Define DEBUG_QSORT at the top of this file and recompile to compile
30 * in code that verifies that the array is sorted.
31 */
32
33 #define GDS_QSORT_CUTOFF 12
34
35 namespace {
36 template <typename INT> void GDS_SWAP(INT *V, size_t I, size_t J)
37 {
38 INT _t = V[I];
39 V[I] = V[J];
40 V[J] = _t;
41 }
42
43 template <typename INT> INT gds_imedian3(const INT v[], INT iv[], size_t left, size_t right)
44 {
45 size_t center = (left + right) / 2;
46
47 if (v[iv[left]] > v[iv[center]]) {
48 GDS_SWAP(iv, left, center);
49 }
50 if (v[iv[left]] > v[iv[right]]) {
51 GDS_SWAP(iv, left, right);
52 }
53 if (v[iv[center]] > v[iv[right]]) {
54 GDS_SWAP(iv, center, right);
55 }
56
57 GDS_SWAP(iv, center, right - 1);
58 return iv[right - 1];
59 }
60
61 template <typename INT> void gds_iqsort(const INT v[], INT iv[], size_t left, size_t right)
62 {
63 if (left + GDS_QSORT_CUTOFF <= right) {
64 size_t pivot = gds_imedian3(v, iv, left, right);
65 size_t i = left;
66 size_t j = right - 1;
67
68 for (;;) {
69 while (v[iv[++i]] < v[pivot]) {
70 ;
71 }
72 while (v[iv[--j]] > v[pivot]) {
73 ;
74 }
75 if (i < j) {
76 GDS_SWAP(iv, i, j);
77 }
78 else {
79 break;
80 }
81 }
82
83 GDS_SWAP(iv, i, right - 1);
84 gds_iqsort(v, iv, left, i - 1);
85 gds_iqsort(v, iv, i + 1, right);
86 }
87 }
88
89 template <typename INT> void gds_iisort(const INT v[], INT iv[], size_t N)
90 {
91 if (N == 0) {
92 return;
93 }
94
95 size_t ndx = 0;
96 INT low = v[iv[0]];
97 for (size_t i = 1; i < N; i++) {
98 if (v[iv[i]] < low) {
99 low = v[iv[i]];
100 ndx = i;
101 }
102 }
103 /* Put lowest value in slot 0 */
104 GDS_SWAP(iv, 0, ndx);
105
106 for (size_t i = 1; i < N; i++) {
107 INT tmp = iv[i];
108 size_t j;
109 for (j = i; v[tmp] < v[iv[j - 1]]; j--) {
110 iv[j] = iv[j - 1];
111 }
112 iv[j] = tmp;
113 }
114 }
115
116 /*
117 * Sort the values in 'v' using the index array 'iv'.
118 * The values in 'v' will be unchanged, but the lowest
119 * value will be v[iv[0]] and the largest v[iv[N-1]]
120 *
121 * The 'iv' array should be initialized 0..N-1 on entry.
122 */
123
124 template <typename INT> size_t gds_median3(INT v[], size_t left, size_t right)
125 {
126 size_t center = (left + right) / 2;
127
128 if (v[left] > v[center]) {
129 GDS_SWAP(v, left, center);
130 }
131 if (v[left] > v[right]) {
132 GDS_SWAP(v, left, right);
133 }
134 if (v[center] > v[right]) {
135 GDS_SWAP(v, center, right);
136 }
137
138 GDS_SWAP(v, center, right - 1);
139 return right - 1;
140 }
141
142 template <typename INT> void gds_qsort(INT v[], size_t left, size_t right)
143 {
144 if (left + GDS_QSORT_CUTOFF <= right) {
145 size_t pivot = gds_median3(v, left, right);
146 size_t i = left;
147 size_t j = right - 1;
148
149 for (;;) {
150 while (v[++i] < v[pivot]) {
151 ;
152 }
153 while (v[--j] > v[pivot]) {
154 ;
155 }
156 if (i < j) {
157 GDS_SWAP(v, i, j);
158 }
159 else {
160 break;
161 }
162 }
163
164 GDS_SWAP(v, i, right - 1);
165 gds_qsort(v, left, i - 1);
166 gds_qsort(v, i + 1, right);
167 }
168 }
169
170 template <typename INT> void gds_isort(INT v[], size_t N)
171 {
172 if (N <= 1) {
173 return;
174 }
175 INT low = v[0];
176 size_t ndx = 0;
177
178 for (size_t i = 1; i < N; i++) {
179 if (v[i] < low) {
180 low = v[i];
181 ndx = i;
182 }
183 }
184 /* Put lowest value in slot 0 */
185 GDS_SWAP(v, 0, ndx);
186
187 for (size_t i = 1; i < N; i++) {
188 INT tmp = v[i];
189 size_t j;
190 for (j = i; tmp < v[j - 1]; j--) {
191 v[j] = v[j - 1];
192 }
193 v[j] = tmp;
194 }
195 }
196
197 template <typename INT> void siftDown(INT *v, INT *iv, size_t start, size_t end)
198 {
199 size_t root = start;
200
201 while (root * 2 + 1 < end) {
202 size_t child = 2 * root + 1;
203 if ((child + 1 < end) && (v[iv[child]] < v[iv[child + 1]])) {
204 child += 1;
205 }
206 if (v[iv[root]] < v[iv[child]]) {
207 GDS_SWAP(iv, child, root);
208 root = child;
209 }
210 else {
211 return;
212 }
213 }
214 }
215 } // namespace
216
217 /*
218 * Sort the values in 'v'
219 */
220
221 template <typename INT> void indexed_sort(INT v[], INT iv[], size_t N)
222 {
223 if (N <= 1) {
224 return;
225 }
226
227 /* heapify */
228 int64_t count = N;
229 for (int64_t start = (count - 2) / 2; start >= 0; start--) {
230 siftDown(v, iv, start, count);
231 }
232
233 for (int64_t end = count - 1; end > 0; end--) {
234 GDS_SWAP(iv, end, 0);
235 siftDown(v, iv, 0, end);
236 }
237
238 #if DEBUG_SORT
239 fmt::print(stderr, "Checking sort of {} values\n", fmt::group_digits(count + 1));
240 for (size_t i = 1; i < N; i++) {
241 assert(v[iv[i - 1]] <= v[iv[i]]);
242 }
243 #endif
244 }
245
246 template <typename INT> void gds_iqsort(const INT v[], INT iv[], size_t N)
247 {
248 if (N <= 1) {
249 return;
250 }
251 gds_iqsort(v, iv, 0, N - 1);
252 gds_iisort(v, iv, N);
253
254 #if defined(DEBUG_QSORT)
255 fmt::print(stderr, "Checking sort of {} values\n", fmt::group_digits(N + 1));
256 size_t i;
257 for (i = 1; i < N; i++) {
258 assert(v[iv[i - 1]] <= v[iv[i]]);
259 }
260 #endif
261 }
262
263 template <typename INT> void gds_qsort(INT v[], size_t N)
264 {
265 if (N <= 1) {
266 return;
267 }
268 gds_qsort(v, 0, N - 1);
269 gds_isort(v, N);
270
271 #if defined(DEBUG_QSORT)
272 fmt::print(stderr, "Checking sort of {} values\n", fmt::group_digits(N + 1));
273 for (size_t i = 1; i < N; i++) {
274 assert(v[i - 1] <= v[i]);
275 }
276 #endif
277 }
278
279 template void gds_iqsort(const int v[], int iv[], size_t N);
280 template void gds_qsort(int v[], size_t N);
281
282 template void gds_iqsort(const int64_t v[], int64_t iv[], size_t N);
283 template void gds_qsort(int64_t v[], size_t N);
284
285 template void indexed_sort(int v[], int iv[], size_t N);
286 template void indexed_sort(int64_t v[], int64_t iv[], size_t N);