1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.numbers.arrays;
18
19 import java.util.Arrays;
20
21 /**
22 * Support class for sorting arrays.
23 *
24 * <p>Optimal sorting networks are used for small fixed size array sorting.
25 *
26 * <p>Note: Requires that the floating-point data contains no NaN values; sorting
27 * does not respect the order of signed zeros imposed by {@link Double#compare(double, double)}.
28 *
29 * @see <a href="https://en.wikipedia.org/wiki/Sorting_network">Sorting network (Wikipedia)</a>
30 * @see <a href="https://bertdobbelaere.github.io/sorting_networks.html">Sorting Networks (Bert Dobbelaere)</a>
31 *
32 * @since 1.2
33 */
34 final class Sorting {
35
36 /** No instances. */
37 private Sorting() {}
38
39 /**
40 * Sorts an array using an insertion sort.
41 *
42 * @param x Data array.
43 * @param left Lower bound (inclusive).
44 * @param right Upper bound (inclusive).
45 */
46 static void sort(double[] x, int left, int right) {
47 for (int i = left; ++i <= right;) {
48 final double v = x[i];
49 // Move preceding higher elements above (if required)
50 if (v < x[i - 1]) {
51 int j = i;
52 while (--j >= left && v < x[j]) {
53 x[j + 1] = x[j];
54 }
55 x[j + 1] = v;
56 }
57 }
58 }
59
60 /**
61 * Sorts the elements at the given distinct indices in an array.
62 *
63 * @param x Data array.
64 * @param a Index.
65 * @param b Index.
66 * @param c Index.
67 */
68 static void sort3(double[] x, int a, int b, int c) {
69 // Decision tree avoiding swaps:
70 // Order [(0,2)]
71 // Move point 1 above point 2 or below point 0
72 final double u = x[a];
73 final double v = x[b];
74 final double w = x[c];
75 if (w < u) {
76 if (v < w) {
77 x[a] = v;
78 x[b] = w;
79 x[c] = u;
80 return;
81 }
82 if (u < v) {
83 x[a] = w;
84 x[b] = u;
85 x[c] = v;
86 return;
87 }
88 // w < v < u
89 x[a] = w;
90 x[c] = u;
91 return;
92 }
93 if (v < u) {
94 // v < u < w
95 x[a] = v;
96 x[b] = u;
97 return;
98 }
99 if (w < v) {
100 // u < w < v
101 x[b] = w;
102 x[c] = v;
103 }
104 // u < v < w
105 }
106
107 /**
108 * Sorts the elements at the given distinct indices in an array.
109 *
110 * @param x Data array.
111 * @param a Index.
112 * @param b Index.
113 * @param c Index.
114 * @param d Index.
115 * @param e Index.
116 */
117 static void sort5(double[] x, int a, int b, int c, int d, int e) {
118 // Uses an optimal sorting network from Knuth's Art of Computer Programming.
119 // 9 comparisons.
120 // Order pairs:
121 // [(0,3),(1,4)]
122 // [(0,2),(1,3)]
123 // [(0,1),(2,4)]
124 // [(1,2),(3,4)]
125 // [(2,3)]
126 if (x[e] < x[b]) {
127 final double u = x[e];
128 x[e] = x[b];
129 x[b] = u;
130 }
131 if (x[d] < x[a]) {
132 final double v = x[d];
133 x[d] = x[a];
134 x[a] = v;
135 }
136
137 if (x[d] < x[b]) {
138 final double u = x[d];
139 x[d] = x[b];
140 x[b] = u;
141 }
142 if (x[c] < x[a]) {
143 final double v = x[c];
144 x[c] = x[a];
145 x[a] = v;
146 }
147
148 if (x[e] < x[c]) {
149 final double u = x[e];
150 x[e] = x[c];
151 x[c] = u;
152 }
153 if (x[b] < x[a]) {
154 final double v = x[b];
155 x[b] = x[a];
156 x[a] = v;
157 }
158
159 if (x[e] < x[d]) {
160 final double u = x[e];
161 x[e] = x[d];
162 x[d] = u;
163 }
164 if (x[c] < x[b]) {
165 final double v = x[c];
166 x[c] = x[b];
167 x[b] = v;
168 }
169
170 if (x[d] < x[c]) {
171 final double u = x[d];
172 x[d] = x[c];
173 x[c] = u;
174 }
175 }
176
177 /**
178 * Place the lower median of 4 elements in {@code b}; the smaller element in
179 * {@code a}; and the larger two elements in {@code c, d}.
180 *
181 * @param x Values
182 * @param a Index.
183 * @param b Index.
184 * @param c Index.
185 * @param d Index.
186 */
187 static void lowerMedian4(double[] x, int a, int b, int c, int d) {
188 // 3 to 5 comparisons
189 if (x[d] < x[b]) {
190 final double u = x[d];
191 x[d] = x[b];
192 x[b] = u;
193 }
194 if (x[c] < x[a]) {
195 final double v = x[c];
196 x[c] = x[a];
197 x[a] = v;
198 }
199 // a--c
200 // b--d
201 if (x[c] < x[b]) {
202 final double u = x[c];
203 x[c] = x[b];
204 x[b] = u;
205 } else if (x[b] < x[a]) {
206 // a--c
207 // b--d
208 final double xb = x[a];
209 x[a] = x[b];
210 x[b] = xb;
211 // b--c
212 // a--d
213 if (x[d] < xb) {
214 x[b] = x[d];
215 // Move a pair to maintain the sorted order
216 x[d] = x[c];
217 x[c] = xb;
218 }
219 }
220 }
221
222 /**
223 * Place the upper median of 4 elements in {@code c}; the smaller two elements in
224 * {@code a,b}; and the larger element in {@code d}.
225 *
226 * @param x Values
227 * @param a Index.
228 * @param b Index.
229 * @param c Index.
230 * @param d Index.
231 */
232 static void upperMedian4(double[] x, int a, int b, int c, int d) {
233 // 3 to 5 comparisons
234 if (x[d] < x[b]) {
235 final double u = x[d];
236 x[d] = x[b];
237 x[b] = u;
238 }
239 if (x[c] < x[a]) {
240 final double v = x[c];
241 x[c] = x[a];
242 x[a] = v;
243 }
244 // a--c
245 // b--d
246 if (x[b] > x[c]) {
247 final double u = x[c];
248 x[c] = x[b];
249 x[b] = u;
250 } else if (x[c] > x[d]) {
251 // a--c
252 // b--d
253 final double xc = x[d];
254 x[d] = x[c];
255 x[c] = xc;
256 // a--d
257 // b--c
258 if (x[a] > xc) {
259 x[c] = x[a];
260 // Move a pair to maintain the sorted order
261 x[a] = x[b];
262 x[b] = xc;
263 }
264 }
265 }
266
267 /**
268 * Sorts an array using an insertion sort.
269 *
270 * @param x Data array.
271 * @param left Lower bound (inclusive).
272 * @param right Upper bound (inclusive).
273 */
274 static void sort(int[] x, int left, int right) {
275 for (int i = left; ++i <= right;) {
276 final int v = x[i];
277 // Move preceding higher elements above (if required)
278 if (v < x[i - 1]) {
279 int j = i;
280 while (--j >= left && v < x[j]) {
281 x[j + 1] = x[j];
282 }
283 x[j + 1] = v;
284 }
285 }
286 }
287
288 /**
289 * Sorts the elements at the given distinct indices in an array.
290 *
291 * @param x Data array.
292 * @param a Index.
293 * @param b Index.
294 * @param c Index.
295 */
296 static void sort3(int[] x, int a, int b, int c) {
297 // Decision tree avoiding swaps:
298 // Order [(0,2)]
299 // Move point 1 above point 2 or below point 0
300 final int u = x[a];
301 final int v = x[b];
302 final int w = x[c];
303 if (w < u) {
304 if (v < w) {
305 x[a] = v;
306 x[b] = w;
307 x[c] = u;
308 return;
309 }
310 if (u < v) {
311 x[a] = w;
312 x[b] = u;
313 x[c] = v;
314 return;
315 }
316 // w < v < u
317 x[a] = w;
318 x[c] = u;
319 return;
320 }
321 if (v < u) {
322 // v < u < w
323 x[a] = v;
324 x[b] = u;
325 return;
326 }
327 if (w < v) {
328 // u < w < v
329 x[b] = w;
330 x[c] = v;
331 }
332 // u < v < w
333 }
334
335 /**
336 * Sorts the elements at the given distinct indices in an array.
337 *
338 * @param x Data array.
339 * @param a Index.
340 * @param b Index.
341 * @param c Index.
342 * @param d Index.
343 * @param e Index.
344 */
345 static void sort5(int[] x, int a, int b, int c, int d, int e) {
346 // Uses an optimal sorting network from Knuth's Art of Computer Programming.
347 // 9 comparisons.
348 // Order pairs:
349 // [(0,3),(1,4)]
350 // [(0,2),(1,3)]
351 // [(0,1),(2,4)]
352 // [(1,2),(3,4)]
353 // [(2,3)]
354 if (x[e] < x[b]) {
355 final int u = x[e];
356 x[e] = x[b];
357 x[b] = u;
358 }
359 if (x[d] < x[a]) {
360 final int v = x[d];
361 x[d] = x[a];
362 x[a] = v;
363 }
364
365 if (x[d] < x[b]) {
366 final int u = x[d];
367 x[d] = x[b];
368 x[b] = u;
369 }
370 if (x[c] < x[a]) {
371 final int v = x[c];
372 x[c] = x[a];
373 x[a] = v;
374 }
375
376 if (x[e] < x[c]) {
377 final int u = x[e];
378 x[e] = x[c];
379 x[c] = u;
380 }
381 if (x[b] < x[a]) {
382 final int v = x[b];
383 x[b] = x[a];
384 x[a] = v;
385 }
386
387 if (x[e] < x[d]) {
388 final int u = x[e];
389 x[e] = x[d];
390 x[d] = u;
391 }
392 if (x[c] < x[b]) {
393 final int v = x[c];
394 x[c] = x[b];
395 x[b] = v;
396 }
397
398 if (x[d] < x[c]) {
399 final int u = x[d];
400 x[d] = x[c];
401 x[c] = u;
402 }
403 }
404
405 /**
406 * Place the lower median of 4 elements in {@code b}; the smaller element in
407 * {@code a}; and the larger two elements in {@code c, d}.
408 *
409 * @param x Values
410 * @param a Index.
411 * @param b Index.
412 * @param c Index.
413 * @param d Index.
414 */
415 static void lowerMedian4(int[] x, int a, int b, int c, int d) {
416 // 3 to 5 comparisons
417 if (x[d] < x[b]) {
418 final int u = x[d];
419 x[d] = x[b];
420 x[b] = u;
421 }
422 if (x[c] < x[a]) {
423 final int v = x[c];
424 x[c] = x[a];
425 x[a] = v;
426 }
427 // a--c
428 // b--d
429 if (x[c] < x[b]) {
430 final int u = x[c];
431 x[c] = x[b];
432 x[b] = u;
433 } else if (x[b] < x[a]) {
434 // a--c
435 // b--d
436 final int xb = x[a];
437 x[a] = x[b];
438 x[b] = xb;
439 // b--c
440 // a--d
441 if (x[d] < xb) {
442 x[b] = x[d];
443 // Move a pair to maintain the sorted order
444 x[d] = x[c];
445 x[c] = xb;
446 }
447 }
448 }
449
450 /**
451 * Place the upper median of 4 elements in {@code c}; the smaller two elements in
452 * {@code a,b}; and the larger element in {@code d}.
453 *
454 * @param x Values
455 * @param a Index.
456 * @param b Index.
457 * @param c Index.
458 * @param d Index.
459 */
460 static void upperMedian4(int[] x, int a, int b, int c, int d) {
461 // 3 to 5 comparisons
462 if (x[d] < x[b]) {
463 final int u = x[d];
464 x[d] = x[b];
465 x[b] = u;
466 }
467 if (x[c] < x[a]) {
468 final int v = x[c];
469 x[c] = x[a];
470 x[a] = v;
471 }
472 // a--c
473 // b--d
474 if (x[b] > x[c]) {
475 final int u = x[c];
476 x[c] = x[b];
477 x[b] = u;
478 } else if (x[c] > x[d]) {
479 // a--c
480 // b--d
481 final int xc = x[d];
482 x[d] = x[c];
483 x[c] = xc;
484 // a--d
485 // b--c
486 if (x[a] > xc) {
487 x[c] = x[a];
488 // Move a pair to maintain the sorted order
489 x[a] = x[b];
490 x[b] = xc;
491 }
492 }
493 }
494
495 /**
496 * Sort the unique indices in-place to the start of the array. The number of
497 * unique indices is returned.
498 *
499 * <p>Uses an insertion sort modified to ignore duplicates. Use on small {@code n}.
500 *
501 * <p>Warning: Requires {@code n > 0}. The array contents after the count of unique
502 * indices {@code c} are unchanged (i.e. {@code [c, n)}. This may change the count of
503 * each unique index in the entire array.
504 *
505 * @param x Indices.
506 * @param n Number of indices.
507 * @return the number of unique indices
508 */
509 static int insertionSortIndices(int[] x, int n) {
510 // Index of last unique value
511 int unique = 0;
512 // Do an insertion sort but only compare the current set of unique values.
513 for (int i = 0; ++i < n;) {
514 final int v = x[i];
515 int j = unique;
516 if (v > x[j]) {
517 // Insert at end
518 x[++unique] = v;
519 } else if (v < x[j]) {
520 // Find insertion point in the unique indices
521 do {
522 --j;
523 } while (j >= 0 && v < x[j]);
524 // Insertion point = j + 1
525 // Insert if at start or non-duplicate
526 if (j < 0 || v != x[j]) {
527 // Move (j, unique] to (j+1, unique+1]
528 for (int k = unique; k > j; --k) {
529 x[k + 1] = x[k];
530 }
531 x[j + 1] = v;
532 ++unique;
533 }
534 }
535 }
536 return unique + 1;
537 }
538
539 /**
540 * Sort the unique indices in-place to the start of the array. The number of
541 * unique indices is returned.
542 *
543 * <p>Uses an Order(1) data structure to ignore duplicates.
544 *
545 * <p>Warning: Requires {@code n > 0}. The array contents after the count of unique
546 * indices {@code c} are unchanged (i.e. {@code [c, n)}. This may change the count of
547 * each unique index in the entire array.
548 *
549 * @param x Indices.
550 * @param n Number of indices.
551 * @return the number of unique indices
552 */
553 static int sortIndices(int[] x, int n) {
554 // Duplicates are checked using a primitive hash set.
555 // Storage (bytes) = 4 * next-power-of-2(n*2) => 2-4 times n
556 final HashIndexSet set = HashIndexSet.create(n);
557 int i = 0;
558 int last = 0;
559 set.add(x[0]);
560 while (++i < n) {
561 final int v = x[i];
562 if (set.add(v)) {
563 x[++last] = v;
564 }
565 }
566 Arrays.sort(x, 0, ++last);
567 return last;
568 }
569 }