1 /*
2 * Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package com.irurueta.sorting;
17
18 import java.util.Comparator;
19
20 /**
21 * Sorts instances of type T in provided arrays using Quicksort method.
22 *
23 * @param <T> Type of instances being sorted.
24 * <p>
25 * This class is based on algorithm found at
26 * Numerical Recipes. 3rd Edition. Cambridge Press. Chapter 8. p. 424
27 * Sedgewick, R. 1978. "Implementing Quicksort Programs", Communications
28 * of the ACM, vol. 21, pp. 847-857.
29 */
30 @SuppressWarnings("Duplicates")
31 public class QuicksortSorter<T> extends Sorter<T> {
32
33 /**
34 * Constant defining size of smallest subarrays to be ordered using
35 * straight insertion.
36 */
37 private static final int M = 7;
38
39 /**
40 * Constant defining size of stack.
41 */
42 private static final int NSTACK = 64;
43
44 /**
45 * Sorts provided array in ascending order so that {@code
46 * array[i - 1] < array[i]} for any valid i.
47 * This method modifies provided array so that
48 * after execution of this method array elements are ordered.
49 *
50 * @param array Array to be sorted. After execution of this method
51 * elements in array between fromIndex (inclusive) and toIndex
52 * (exclusive) are modified so that they are on ascending order.
53 * @param fromIndex Index were sorting starts (inclusive).
54 * @param toIndex Index were sorting stops (exclusive).
55 * @param comparator Determines whether an element is greater or lower
56 * than another one.
57 * @throws SortingException If for some reason sorting fails.
58 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
59 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
60 * {@code toIndex > array.length}.
61 */
62 @Override
63 public void sort(final T[] array, final int fromIndex, final int toIndex, final Comparator<T> comparator)
64 throws SortingException {
65
66 if (fromIndex > toIndex) {
67 throw new IllegalArgumentException();
68 }
69 if (fromIndex < 0 || toIndex > array.length) {
70 throw new ArrayIndexOutOfBoundsException();
71 }
72 if (fromIndex == toIndex) {
73 return;
74 }
75
76 final var n = toIndex - fromIndex;
77
78 int i;
79 int j;
80 int ir;
81 int k;
82 var jstack = -1;
83 var l = 0;
84 T a;
85 final var istack = new int[NSTACK];
86 ir = n - 1;
87
88 for (; ; ) {
89 // Insertion sort when subarray is small enough
90 if (ir - l < M) {
91 for (j = l + 1; j <= ir; j++) {
92 a = array[j + fromIndex];
93 for (i = j - 1; i >= l; i--) {
94 if (comparator.compare(array[i + fromIndex], a) <= 0) {
95 break;
96 }
97 array[i + 1 + fromIndex] = array[i + fromIndex];
98 }
99 array[i + 1 + fromIndex] = a;
100 }
101 if (jstack < 0) {
102 break;
103 }
104 // Pop stack and begin a new round of partitioning
105 ir = istack[jstack--];
106 l = istack[jstack--];
107 } else {
108 // Choose median of left, center, and right elements as
109 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
110 // <= a(ir)
111 k = (l + ir) >> 1;
112 swap(array, k + fromIndex, l + 1 + fromIndex);
113 if (comparator.compare(array[l + fromIndex], array[ir + fromIndex]) > 0) {
114 swap(array, l + fromIndex, ir + fromIndex);
115 }
116 if (comparator.compare(array[l + 1 + fromIndex], array[ir + fromIndex]) > 0) {
117 swap(array, l + 1 + fromIndex, ir + fromIndex);
118 }
119 if (comparator.compare(array[l + fromIndex], array[l + 1 + fromIndex]) > 0) {
120 swap(array, l + fromIndex, l + 1 + fromIndex);
121 }
122 // Initialize pointers for partitioning
123 i = l + 1;
124 j = ir;
125 // Partitioning element
126 a = array[l + 1 + fromIndex];
127 // Beginning of innermost loop
128 for (; ; ) {
129 // Scan up to find element > a
130 do {
131 i++;
132 } while (comparator.compare(array[i + fromIndex], a) < 0);
133 // Scan down to find element < a
134 do {
135 j--;
136 } while (comparator.compare(array[j + fromIndex], a) > 0);
137 // Pointers crossed. Partitioning complete
138 if (j < i) {
139 break;
140 }
141 // Exchange elements
142 swap(array, i + fromIndex, j + fromIndex);
143 // End of innermost loop
144 }
145 // Insert partitioning element
146 array[l + 1 + fromIndex] = array[j + fromIndex];
147 array[j + fromIndex] = a;
148 jstack += 2;
149 // NSTACK too small in sort
150 if (jstack >= NSTACK) {
151 throw new SortingException();
152 }
153 // Push pointers to larger subarray on stack; process smaller
154 // subarray immediately
155 if (ir - i + 1 >= j - l) {
156 istack[jstack] = ir;
157 istack[jstack - 1] = i;
158 ir = j - 1;
159 } else {
160 istack[jstack] = j - 1;
161 istack[jstack - 1] = l;
162 l = i;
163 }
164 }
165 }
166 }
167
168 /**
169 * Sorts provided array in ascending order so that {@code
170 * array[i - 1] < array[i]} for any valid i.
171 * This method modifies provided array so that
172 * after execution of this method array elements are ordered.
173 * An array containing the original indices where elements were
174 * located is returned so that other arrays or collections can be kept
175 * in the same order.
176 *
177 * @param array Array to be sorted. After execution of this method
178 * elements in array between fromIndex (inclusive) and toIndex
179 * (exclusive) are modified so that they are on ascending order.
180 * @param fromIndex Index were sorting starts (inclusive).
181 * @param toIndex Index were sorting stops (exclusive).
182 * @param comparator Determines whether an element is greater or lower
183 * than another one.
184 * @return Array containing original location of elements that have been
185 * sorted. Only elements between fromIndex (inclusive) and toIndex
186 * (exclusive) are modified, the remaining ones are kept in natural
187 * order.
188 * @throws SortingException If for some reason sorting fails.
189 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
190 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
191 * {@code toIndex > array.length}.
192 */
193 @Override
194 public int[] sortWithIndices(final T[] array, final int fromIndex, final int toIndex,
195 final Comparator<T> comparator) throws SortingException {
196
197 if (fromIndex > toIndex) {
198 throw new IllegalArgumentException();
199 }
200 if (fromIndex < 0 || toIndex > array.length) {
201 throw new ArrayIndexOutOfBoundsException();
202 }
203
204 final int[] indices = getInitialIndicesVector(array.length);
205 if (fromIndex == toIndex) {
206 return indices;
207 }
208
209 final int n = toIndex - fromIndex;
210
211 int i;
212 int j;
213 int ir;
214 int k;
215 var jstack = -1;
216 var l = 0;
217 T a;
218 int b;
219 final var istack = new int[NSTACK];
220 ir = n - 1;
221
222 for (; ; ) {
223 // Insertion sort when subarray is small enough
224 if (ir - l < M) {
225 for (j = l + 1; j <= ir; j++) {
226 a = array[j + fromIndex];
227 b = indices[j + fromIndex];
228 for (i = j - 1; i >= l; i--) {
229 if (comparator.compare(array[i + fromIndex], a) <= 0) {
230 break;
231 }
232 array[i + 1 + fromIndex] = array[i + fromIndex];
233 indices[i + 1 + fromIndex] = indices[i + fromIndex];
234 }
235 array[i + 1 + fromIndex] = a;
236 indices[i + 1 + fromIndex] = b;
237 }
238 if (jstack < 0) {
239 break;
240 }
241 // Pop stack and begin a new round of partitioning
242 ir = istack[jstack--];
243 l = istack[jstack--];
244 } else {
245 // Choose median of left, center, and right elements as
246 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
247 // <= a(ir)
248 k = (l + ir) >> 1;
249 swap(array, k + fromIndex, l + 1 + fromIndex);
250 swapIndices(indices, k + fromIndex, l + 1 + fromIndex);
251 if (comparator.compare(array[l + fromIndex], array[ir + fromIndex]) > 0) {
252 swap(array, l + fromIndex, ir + fromIndex);
253 swapIndices(indices, l + fromIndex, ir + fromIndex);
254 }
255 if (comparator.compare(array[l + 1 + fromIndex], array[ir + fromIndex]) > 0) {
256 swap(array, l + 1 + fromIndex, ir + fromIndex);
257 swapIndices(indices, l + 1 + fromIndex, ir + fromIndex);
258 }
259 if (comparator.compare(array[l + fromIndex], array[l + 1 + fromIndex]) > 0) {
260 swap(array, l + fromIndex, l + 1 + fromIndex);
261 swapIndices(indices, l + fromIndex, l + 1 + fromIndex);
262 }
263 // Initialize pointers for partitioning
264 i = l + 1;
265 j = ir;
266 // Partitioning element
267 a = array[l + 1 + fromIndex];
268 b = indices[l + 1 + fromIndex];
269 // Beginning of innermost loop
270 for (; ; ) {
271 // Scan up to find element > a
272 do {
273 i++;
274 } while (comparator.compare(array[i + fromIndex], a) < 0);
275 // Scan down to find element < a
276 do {
277 j--;
278 } while (comparator.compare(array[j + fromIndex], a) > 0);
279 // Pointers crossed. Partitioning complete
280 if (j < i) {
281 break;
282 }
283 // Exchange elements
284 swap(array, i + fromIndex, j + fromIndex);
285 swapIndices(indices, i + fromIndex, j + fromIndex);
286 // End of innermost loop
287 }
288 // Insert partitioning element
289 array[l + 1 + fromIndex] = array[j + fromIndex];
290 array[j + fromIndex] = a;
291 indices[l + 1 + fromIndex] = indices[j + fromIndex];
292 indices[j + fromIndex] = b;
293 jstack += 2;
294 // NSTACK too small in sort
295 if (jstack >= NSTACK) {
296 throw new SortingException();
297 }
298 // Push pointers to larger subarray on stack; process smaller
299 // subarray immediately
300 if (ir - i + 1 >= j - l) {
301 istack[jstack] = ir;
302 istack[jstack - 1] = i;
303 ir = j - 1;
304 } else {
305 istack[jstack] = j - 1;
306 istack[jstack - 1] = l;
307 l = i;
308 }
309 }
310 }
311
312 return indices;
313 }
314
315 /**
316 * Returns sorting method of this class.
317 *
318 * @return Sorting method.
319 */
320 @Override
321 public SortingMethod getMethod() {
322 return SortingMethod.QUICKSORT_SORTING_METHOD;
323 }
324
325 /**
326 * Sorts provided array in ascending order so that {@code
327 * array[i - 1] < array[i]} for any valid i.
328 * This method modifies provided array so that
329 * after execution of this method array elements are ordered.
330 *
331 * @param array Array to be sorted. After execution of this method
332 * elements in array between fromIndex (inclusive) and toIndex
333 * (exclusive) are modified so that they are on ascending order.
334 * @param fromIndex Index were sorting starts (inclusive).
335 * @param toIndex Index were sorting stops (exclusive).
336 * @throws SortingException If for some reason sorting fails.
337 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
338 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
339 * {@code toIndex > array.length}.
340 */
341 @Override
342 public void sort(final double[] array, final int fromIndex, final int toIndex) throws SortingException {
343
344 if (fromIndex > toIndex) {
345 throw new IllegalArgumentException();
346 }
347 if (fromIndex < 0 || toIndex > array.length) {
348 throw new ArrayIndexOutOfBoundsException();
349 }
350 if (fromIndex == toIndex) {
351 return;
352 }
353
354 final int n = toIndex - fromIndex;
355
356 int i;
357 int j;
358 int ir;
359 int k;
360 var jstack = -1;
361 var l = 0;
362 double a;
363 final var istack = new int[NSTACK];
364 ir = n - 1;
365
366 for (; ; ) {
367 // Insertion sort when subarray is small enough
368 if (ir - l < M) {
369 for (j = l + 1; j <= ir; j++) {
370 a = array[j + fromIndex];
371 for (i = j - 1; i >= l; i--) {
372 if (array[i + fromIndex] <= a) {
373 break;
374 }
375 array[i + 1 + fromIndex] = array[i + fromIndex];
376 }
377 array[i + 1 + fromIndex] = a;
378 }
379 if (jstack < 0) {
380 break;
381 }
382 // Pop stack and begin a new round of partitioning
383 ir = istack[jstack--];
384 l = istack[jstack--];
385 } else {
386 // Choose median of left, center, and right elements as
387 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
388 // <= a(ir)
389 k = (l + ir) >> 1;
390 swap(array, k + fromIndex, l + 1 + fromIndex);
391 if (array[l + fromIndex] > array[ir + fromIndex]) {
392 swap(array, l + fromIndex, ir + fromIndex);
393 }
394 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
395 swap(array, l + 1 + fromIndex, ir + fromIndex);
396 }
397 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
398 swap(array, l + fromIndex, l + 1 + fromIndex);
399 }
400 // Initialize pointers for partitioning
401 i = l + 1;
402 j = ir;
403 // Partitioning element
404 a = array[l + 1 + fromIndex];
405 // Beginning of innermost loop
406 for (; ; ) {
407 // Scan up to find element > a
408 do {
409 i++;
410 } while (array[i + fromIndex] < a);
411 // Scan down to find element < a
412 do {
413 j--;
414 } while (array[j + fromIndex] > a);
415 // Pointers crossed. Partitioning complete
416 if (j < i) {
417 break;
418 }
419 // Exchange elements
420 swap(array, i + fromIndex, j + fromIndex);
421 // End of innermost loop
422 }
423 // Insert partitioning element
424 array[l + 1 + fromIndex] = array[j + fromIndex];
425 array[j + fromIndex] = a;
426 jstack += 2;
427 // NSTACK too small in sort
428 if (jstack >= NSTACK) {
429 throw new SortingException();
430 }
431 // Push pointers to larger subarray on stack; process smaller
432 // subarray immediately
433 if (ir - i + 1 >= j - l) {
434 istack[jstack] = ir;
435 istack[jstack - 1] = i;
436 ir = j - 1;
437 } else {
438 istack[jstack] = j - 1;
439 istack[jstack - 1] = l;
440 l = i;
441 }
442 }
443 }
444 }
445
446 /**
447 * Sorts provided array in ascending order so that {@code
448 * array[i - 1] < array[i]} for any valid i.
449 * This method modifies provided array so that
450 * after execution of this method array elements are ordered.
451 * An array containing the original indices where elements were
452 * located is returned so that other arrays or collections can be kept
453 * in the same order.
454 *
455 * @param array Array to be sorted. After execution of this method
456 * elements in array between fromIndex (inclusive) and toIndex
457 * (exclusive) are modified so that they are on ascending order.
458 * @param fromIndex Index were sorting starts (inclusive).
459 * @param toIndex Index were sorting stops (exclusive).
460 * @return Array containing original location of elements that have been
461 * sorted. Only elements between fromIndex (inclusive) and toIndex
462 * (exclusive) are modified, the remaining ones are kept in natural
463 * order.
464 * @throws SortingException If for some reason sorting fails.
465 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
466 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
467 * {@code toIndex > array.length}.
468 */
469 @Override
470 public int[] sortWithIndices(final double[] array, final int fromIndex, final int toIndex) throws SortingException {
471
472 if (fromIndex > toIndex) {
473 throw new IllegalArgumentException();
474 }
475 if (fromIndex < 0 || toIndex > array.length) {
476 throw new ArrayIndexOutOfBoundsException();
477 }
478
479 final int[] indices = getInitialIndicesVector(array.length);
480 if (fromIndex == toIndex) {
481 return indices;
482 }
483
484 final int n = toIndex - fromIndex;
485
486 int i;
487 int j;
488 int ir;
489 int k;
490 var jstack = -1;
491 var l = 0;
492 double a;
493 int b;
494 final var istack = new int[NSTACK];
495 ir = n - 1;
496
497 for (; ; ) {
498 // Insertion sort when subarray is small enough
499 if (ir - l < M) {
500 for (j = l + 1; j <= ir; j++) {
501 a = array[j + fromIndex];
502 b = indices[j + fromIndex];
503 for (i = j - 1; i >= l; i--) {
504 if (array[i + fromIndex] <= a) {
505 break;
506 }
507 array[i + 1 + fromIndex] = array[i + fromIndex];
508 indices[i + 1 + fromIndex] = indices[i + fromIndex];
509 }
510 array[i + 1 + fromIndex] = a;
511 indices[i + 1 + fromIndex] = b;
512 }
513 if (jstack < 0) {
514 break;
515 }
516 // Pop stack and begin a new round of partitioning
517 ir = istack[jstack--];
518 l = istack[jstack--];
519 } else {
520 // Choose median of left, center, and right elements as
521 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
522 // <= a(ir)
523 k = (l + ir) >> 1;
524 swap(array, k + fromIndex, l + 1 + fromIndex);
525 swapIndices(indices, k + fromIndex, l + 1 + fromIndex);
526 if (array[l + fromIndex] > array[ir + fromIndex]) {
527 swap(array, l + fromIndex, ir + fromIndex);
528 swapIndices(indices, l + fromIndex, ir + fromIndex);
529 }
530 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
531 swap(array, l + 1 + fromIndex, ir + fromIndex);
532 swapIndices(indices, l + 1 + fromIndex, ir + fromIndex);
533 }
534 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
535 swap(array, l + fromIndex, l + 1 + fromIndex);
536 swapIndices(indices, l + fromIndex, l + 1 + fromIndex);
537 }
538 // Initialize pointers for partitioning
539 i = l + 1;
540 j = ir;
541 // Partitioning element
542 a = array[l + 1 + fromIndex];
543 b = indices[l + 1 + fromIndex];
544 // Beginning of innermost loop
545 for (; ; ) {
546 // Scan up to find element > a
547 do {
548 i++;
549 } while (array[i + fromIndex] < a);
550 // Scan down to find element < a
551 do {
552 j--;
553 } while (array[j + fromIndex] > a);
554 // Pointers crossed. Partitioning complete
555 if (j < i) {
556 break;
557 }
558 // Exchange elements
559 swap(array, i + fromIndex, j + fromIndex);
560 swapIndices(indices, i + fromIndex, j + fromIndex);
561 // End of innermost loop
562 }
563 // Insert partitioning element
564 array[l + 1 + fromIndex] = array[j + fromIndex];
565 array[j + fromIndex] = a;
566 indices[l + 1 + fromIndex] = indices[j + fromIndex];
567 indices[j + fromIndex] = b;
568 jstack += 2;
569 // NSTACK too small in sort
570 if (jstack >= NSTACK) {
571 throw new SortingException();
572 }
573 // Push pointers to larger subarray on stack; process smaller
574 // subarray immediately
575 if (ir - i + 1 >= j - l) {
576 istack[jstack] = ir;
577 istack[jstack - 1] = i;
578 ir = j - 1;
579 } else {
580 istack[jstack] = j - 1;
581 istack[jstack - 1] = l;
582 l = i;
583 }
584 }
585 }
586
587 return indices;
588 }
589
590 /**
591 * Sorts provided array in ascending order so that {@code
592 * array[i - 1] < array[i]} for any valid i.
593 * This method modifies provided array so that
594 * after execution of this method array elements are ordered.
595 *
596 * @param array Array to be sorted. After execution of this method
597 * elements in array between fromIndex (inclusive) and toIndex
598 * (exclusive) are modified so that they are on ascending order.
599 * @param fromIndex Index were sorting starts (inclusive).
600 * @param toIndex Index were sorting stops (exclusive).
601 * @throws SortingException If for some reason sorting fails.
602 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
603 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
604 * {@code toIndex > array.length}.
605 */
606 @Override
607 public void sort(final float[] array, final int fromIndex, final int toIndex) throws SortingException {
608
609 if (fromIndex > toIndex) {
610 throw new IllegalArgumentException();
611 }
612 if (fromIndex < 0 || toIndex > array.length) {
613 throw new ArrayIndexOutOfBoundsException();
614 }
615 if (fromIndex == toIndex) {
616 return;
617 }
618
619 final var n = toIndex - fromIndex;
620
621 int i;
622 int j;
623 int ir;
624 int k;
625 var jstack = -1;
626 var l = 0;
627 float a;
628 final var istack = new int[NSTACK];
629 ir = n - 1;
630
631 for (; ; ) {
632 // Insertion sort when subarray is small enough
633 if (ir - l < M) {
634 for (j = l + 1; j <= ir; j++) {
635 a = array[j + fromIndex];
636 for (i = j - 1; i >= l; i--) {
637 if (array[i + fromIndex] <= a) {
638 break;
639 }
640 array[i + 1 + fromIndex] = array[i + fromIndex];
641 }
642 array[i + 1 + fromIndex] = a;
643 }
644 if (jstack < 0) {
645 break;
646 }
647 // Pop stack and begin a new round of partitioning
648 ir = istack[jstack--];
649 l = istack[jstack--];
650 } else {
651 // Choose median of left, center, and right elements as
652 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
653 // <= a(ir)
654 k = (l + ir) >> 1;
655 swap(array, k + fromIndex, l + 1 + fromIndex);
656 if (array[l + fromIndex] > array[ir + fromIndex]) {
657 swap(array, l + fromIndex, ir + fromIndex);
658 }
659 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
660 swap(array, l + 1 + fromIndex, ir + fromIndex);
661 }
662 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
663 swap(array, l + fromIndex, l + 1 + fromIndex);
664 }
665 // Initialize pointers for partitioning
666 i = l + 1;
667 j = ir;
668 // Partitioning element
669 a = array[l + 1 + fromIndex];
670 // Beginning of innermost loop
671 for (; ; ) {
672 // Scan up to find element > a
673 do {
674 i++;
675 } while (array[i + fromIndex] < a);
676 // Scan down to find element < a
677 do {
678 j--;
679 } while (array[j + fromIndex] > a);
680 // Pointers crossed. Partitioning complete
681 if (j < i) {
682 break;
683 }
684 // Exchange elements
685 swap(array, i + fromIndex, j + fromIndex);
686 // End of innermost loop
687 }
688 // Insert partitioning element
689 array[l + 1 + fromIndex] = array[j + fromIndex];
690 array[j + fromIndex] = a;
691 jstack += 2;
692 // NSTACK too small in sort
693 if (jstack >= NSTACK) {
694 throw new SortingException();
695 }
696 // Push pointers to larger subarray on stack; process smaller
697 // subarray immediately
698 if (ir - i + 1 >= j - l) {
699 istack[jstack] = ir;
700 istack[jstack - 1] = i;
701 ir = j - 1;
702 } else {
703 istack[jstack] = j - 1;
704 istack[jstack - 1] = l;
705 l = i;
706 }
707 }
708 }
709 }
710
711 /**
712 * Sorts provided array in ascending order so that {@code
713 * array[i - 1] < array[i]} for any valid i.
714 * This method modifies provided array so that
715 * after execution of this method array elements are ordered.
716 * An array containing the original indices where elements were
717 * located is returned so that other arrays or collections can be kept
718 * in the same order.
719 *
720 * @param array Array to be sorted. After execution of this method
721 * elements in array between fromIndex (inclusive) and toIndex
722 * (exclusive) are modified so that they are on ascending order.
723 * @param fromIndex Index were sorting starts (inclusive).
724 * @param toIndex Index were sorting stops (exclusive).
725 * @return Array containing original location of elements that have been
726 * sorted. Only elements between fromIndex (inclusive) and toIndex
727 * (exclusive) are modified, the remaining ones are kept in natural
728 * order.
729 * @throws SortingException If for some reason sorting fails.
730 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
731 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
732 * {@code toIndex > array.length}.
733 */
734 @Override
735 public int[] sortWithIndices(final float[] array, final int fromIndex, final int toIndex) throws SortingException {
736
737 if (fromIndex > toIndex) {
738 throw new IllegalArgumentException();
739 }
740 if (fromIndex < 0 || toIndex > array.length) {
741 throw new ArrayIndexOutOfBoundsException();
742 }
743
744 final int[] indices = getInitialIndicesVector(array.length);
745 if (fromIndex == toIndex) {
746 return indices;
747 }
748
749 final var n = toIndex - fromIndex;
750
751 int i;
752 int j;
753 int ir;
754 int k;
755 var jstack = -1;
756 var l = 0;
757 float a;
758 int b;
759 final var istack = new int[NSTACK];
760 ir = n - 1;
761
762 for (; ; ) {
763 // Insertion sort when subarray is small enough
764 if (ir - l < M) {
765 for (j = l + 1; j <= ir; j++) {
766 a = array[j + fromIndex];
767 b = indices[j + fromIndex];
768 for (i = j - 1; i >= l; i--) {
769 if (array[i + fromIndex] <= a) {
770 break;
771 }
772 array[i + 1 + fromIndex] = array[i + fromIndex];
773 indices[i + 1 + fromIndex] = indices[i + fromIndex];
774 }
775 array[i + 1 + fromIndex] = a;
776 indices[i + 1 + fromIndex] = b;
777 }
778 if (jstack < 0) {
779 break;
780 }
781 // Pop stack and begin a new round of partitioning
782 ir = istack[jstack--];
783 l = istack[jstack--];
784 } else {
785 // Choose median of left, center, and right elements as
786 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
787 // <= a(ir)
788 k = (l + ir) >> 1;
789 swap(array, k + fromIndex, l + 1 + fromIndex);
790 swapIndices(indices, k + fromIndex, l + 1 + fromIndex);
791 if (array[l + fromIndex] > array[ir + fromIndex]) {
792 swap(array, l + fromIndex, ir + fromIndex);
793 swapIndices(indices, l + fromIndex, ir + fromIndex);
794 }
795 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
796 swap(array, l + 1 + fromIndex, ir + fromIndex);
797 swapIndices(indices, l + 1 + fromIndex, ir + fromIndex);
798 }
799 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
800 swap(array, l + fromIndex, l + 1 + fromIndex);
801 swapIndices(indices, l + fromIndex, l + 1 + fromIndex);
802 }
803 // Initialize pointers for partitioning
804 i = l + 1;
805 j = ir;
806 // Partitioning element
807 a = array[l + 1 + fromIndex];
808 b = indices[l + 1 + fromIndex];
809 // Beginning of innermost loop
810 for (; ; ) {
811 // Scan up to find element > a
812 do {
813 i++;
814 } while (array[i + fromIndex] < a);
815 // Scan down to find element < a
816 do {
817 j--;
818 } while (array[j + fromIndex] > a);
819 // Pointers crossed. Partitioning complete
820 if (j < i) {
821 break;
822 }
823 // Exchange elements
824 swap(array, i + fromIndex, j + fromIndex);
825 swapIndices(indices, i + fromIndex, j + fromIndex);
826 // End of innermost loop
827 }
828 // Insert partitioning element
829 array[l + 1 + fromIndex] = array[j + fromIndex];
830 array[j + fromIndex] = a;
831 indices[l + 1 + fromIndex] = indices[j + fromIndex];
832 indices[j + fromIndex] = b;
833 jstack += 2;
834 // NSTACK too small in sort
835 if (jstack >= NSTACK) {
836 throw new SortingException();
837 }
838 // Push pointers to larger subarray on stack; process smaller
839 // subarray immediately
840 if (ir - i + 1 >= j - l) {
841 istack[jstack] = ir;
842 istack[jstack - 1] = i;
843 ir = j - 1;
844 } else {
845 istack[jstack] = j - 1;
846 istack[jstack - 1] = l;
847 l = i;
848 }
849 }
850 }
851
852 return indices;
853 }
854
855 /**
856 * Sorts provided array in ascending order so that {@code
857 * array[i - 1] < array[i]} for any valid i.
858 * This method modifies provided array so that
859 * after execution of this method array elements are ordered.
860 *
861 * @param array Array to be sorted. After execution of this method
862 * elements in array between fromIndex (inclusive) and toIndex
863 * (exclusive) are modified so that they are on ascending order.
864 * @param fromIndex Index were sorting starts (inclusive).
865 * @param toIndex Index were sorting stops (exclusive).
866 * @throws SortingException If for some reason sorting fails.
867 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
868 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
869 * {@code toIndex > array.length}.
870 */
871 @Override
872 public void sort(final int[] array, final int fromIndex, final int toIndex) throws SortingException {
873
874 if (fromIndex > toIndex) {
875 throw new IllegalArgumentException();
876 }
877 if (fromIndex < 0 || toIndex > array.length) {
878 throw new ArrayIndexOutOfBoundsException();
879 }
880 if (fromIndex == toIndex) {
881 return;
882 }
883
884 final var n = toIndex - fromIndex;
885
886 int i;
887 int j;
888 int ir;
889 int k;
890 var jstack = -1;
891 var l = 0;
892 int a;
893 final var istack = new int[NSTACK];
894 ir = n - 1;
895
896 for (; ; ) {
897 // Insertion sort when subarray is small enough
898 if (ir - l < M) {
899 for (j = l + 1; j <= ir; j++) {
900 a = array[j + fromIndex];
901 for (i = j - 1; i >= l; i--) {
902 if (array[i + fromIndex] <= a) {
903 break;
904 }
905 array[i + 1 + fromIndex] = array[i + fromIndex];
906 }
907 array[i + 1 + fromIndex] = a;
908 }
909 if (jstack < 0) {
910 break;
911 }
912 // Pop stack and begin a new round of partitioning
913 ir = istack[jstack--];
914 l = istack[jstack--];
915 } else {
916 // Choose median of left, center, and right elements as
917 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
918 // <= a(ir)
919 k = (l + ir) >> 1;
920 swap(array, k + fromIndex, l + 1 + fromIndex);
921 if (array[l + fromIndex] > array[ir + fromIndex]) {
922 swap(array, l + fromIndex, ir + fromIndex);
923 }
924 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
925 swap(array, l + 1 + fromIndex, ir + fromIndex);
926 }
927 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
928 swap(array, l + fromIndex, l + 1 + fromIndex);
929 }
930 // Initialize pointers for partitioning
931 i = l + 1;
932 j = ir;
933 // Partitioning element
934 a = array[l + 1 + fromIndex];
935 // Beginning of innermost loop
936 for (; ; ) {
937 // Scan up to find element > a
938 do {
939 i++;
940 } while (array[i + fromIndex] < a);
941 // Scan down to find element < a
942 do {
943 j--;
944 } while (array[j + fromIndex] > a);
945 // Pointers crossed. Partitioning complete
946 if (j < i) {
947 break;
948 }
949 // Exchange elements
950 swap(array, i + fromIndex, j + fromIndex);
951 // End of innermost loop
952 }
953 // Insert partitioning element
954 array[l + 1 + fromIndex] = array[j + fromIndex];
955 array[j + fromIndex] = a;
956 jstack += 2;
957 // NSTACK too small in sort
958 if (jstack >= NSTACK) {
959 throw new SortingException();
960 }
961 // Push pointers to larger subarray on stack; process smaller
962 // subarray immediately
963 if (ir - i + 1 >= j - l) {
964 istack[jstack] = ir;
965 istack[jstack - 1] = i;
966 ir = j - 1;
967 } else {
968 istack[jstack] = j - 1;
969 istack[jstack - 1] = l;
970 l = i;
971 }
972 }
973 }
974 }
975
976 /**
977 * Sorts provided array in ascending order so that {@code
978 * array[i - 1] < array[i]} for any valid i.
979 * This method modifies provided array so that
980 * after execution of this method array elements are ordered.
981 * An array containing the original indices where elements were
982 * located is returned so that other arrays or collections can be kept
983 * in the same order.
984 *
985 * @param array Array to be sorted. After execution of this method
986 * elements in array between fromIndex (inclusive) and toIndex
987 * (exclusive) are modified so that they are on ascending order.
988 * @param fromIndex Index were sorting starts (inclusive).
989 * @param toIndex Index were sorting stops (exclusive).
990 * @return Array containing original location of elements that have been
991 * sorted. Only elements between fromIndex (inclusive) and toIndex
992 * (exclusive) are modified, the remaining ones are kept in natural
993 * order.
994 * @throws SortingException If for some reason sorting fails.
995 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
996 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
997 * {@code toIndex > array.length}.
998 */
999 @Override
1000 public int[] sortWithIndices(final int[] array, final int fromIndex, final int toIndex) throws SortingException {
1001
1002 if (fromIndex > toIndex) {
1003 throw new IllegalArgumentException();
1004 }
1005 if (fromIndex < 0 || toIndex > array.length) {
1006 throw new ArrayIndexOutOfBoundsException();
1007 }
1008
1009 final int[] indices = getInitialIndicesVector(array.length);
1010 if (fromIndex == toIndex) {
1011 return indices;
1012 }
1013
1014 final var n = toIndex - fromIndex;
1015
1016 int i;
1017 int j;
1018 int ir;
1019 int k;
1020 var jstack = -1;
1021 var l = 0;
1022 int a;
1023 int b;
1024 final var istack = new int[NSTACK];
1025 ir = n - 1;
1026
1027 for (; ; ) {
1028 // Insertion sort when subarray is small enough
1029 if (ir - l < M) {
1030 for (j = l + 1; j <= ir; j++) {
1031 a = array[j + fromIndex];
1032 b = indices[j + fromIndex];
1033 for (i = j - 1; i >= l; i--) {
1034 if (array[i + fromIndex] <= a) {
1035 break;
1036 }
1037 array[i + 1 + fromIndex] = array[i + fromIndex];
1038 indices[i + 1 + fromIndex] = indices[i + fromIndex];
1039 }
1040 array[i + 1 + fromIndex] = a;
1041 indices[i + 1 + fromIndex] = b;
1042 }
1043 if (jstack < 0) {
1044 break;
1045 }
1046 // Pop stack and begin a new round of partitioning
1047 ir = istack[jstack--];
1048 l = istack[jstack--];
1049 } else {
1050 // Choose median of left, center, and right elements as
1051 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
1052 // <= a(ir)
1053 k = (l + ir) >> 1;
1054 swap(array, k + fromIndex, l + 1 + fromIndex);
1055 swapIndices(indices, k + fromIndex, l + 1 + fromIndex);
1056 if (array[l + fromIndex] > array[ir + fromIndex]) {
1057 swap(array, l + fromIndex, ir + fromIndex);
1058 swapIndices(indices, l + fromIndex, ir + fromIndex);
1059 }
1060 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
1061 swap(array, l + 1 + fromIndex, ir + fromIndex);
1062 swapIndices(indices, l + 1 + fromIndex, ir + fromIndex);
1063 }
1064 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
1065 swap(array, l + fromIndex, l + 1 + fromIndex);
1066 swapIndices(indices, l + fromIndex, l + 1 + fromIndex);
1067 }
1068 // Initialize pointers for partitioning
1069 i = l + 1;
1070 j = ir;
1071 // Partitioning element
1072 a = array[l + 1 + fromIndex];
1073 b = indices[l + 1 + fromIndex];
1074 // Beginning of innermost loop
1075 for (; ; ) {
1076 // Scan up to find element > a
1077 do {
1078 i++;
1079 } while (array[i + fromIndex] < a);
1080 // Scan down to find element < a
1081 do {
1082 j--;
1083 } while (array[j + fromIndex] > a);
1084 // Pointers crossed. Partitioning complete
1085 if (j < i) {
1086 break;
1087 }
1088 // Exchange elements
1089 swap(array, i + fromIndex, j + fromIndex);
1090 swapIndices(indices, i + fromIndex, j + fromIndex);
1091 // End of innermost loop
1092 }
1093 // Insert partitioning element
1094 array[l + 1 + fromIndex] = array[j + fromIndex];
1095 array[j + fromIndex] = a;
1096 indices[l + 1 + fromIndex] = indices[j + fromIndex];
1097 indices[j + fromIndex] = b;
1098 jstack += 2;
1099 // NSTACK too small in sort
1100 if (jstack >= NSTACK) {
1101 throw new SortingException();
1102 }
1103 // Push pointers to larger subarray on stack; process smaller
1104 // subarray immediately
1105 if (ir - i + 1 >= j - l) {
1106 istack[jstack] = ir;
1107 istack[jstack - 1] = i;
1108 ir = j - 1;
1109 } else {
1110 istack[jstack] = j - 1;
1111 istack[jstack - 1] = l;
1112 l = i;
1113 }
1114 }
1115 }
1116
1117 return indices;
1118 }
1119
1120 /**
1121 * Sorts provided array in ascending order so that {@code
1122 * array[i - 1] < array[i]} for any valid i.
1123 * This method modifies provided array so that
1124 * after execution of this method array elements are ordered.
1125 *
1126 * @param array Array to be sorted. After execution of this method
1127 * elements in array between fromIndex (inclusive) and toIndex
1128 * (exclusive) are modified so that they are on ascending order.
1129 * @param fromIndex Index were sorting starts (inclusive).
1130 * @param toIndex Index were sorting stops (exclusive).
1131 * @throws SortingException If for some reason sorting fails.
1132 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
1133 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1134 * {@code toIndex > array.length}.
1135 */
1136 @Override
1137 public void sort(final long[] array, final int fromIndex, final int toIndex) throws SortingException {
1138
1139 if (fromIndex > toIndex) {
1140 throw new IllegalArgumentException();
1141 }
1142 if (fromIndex < 0 || toIndex > array.length) {
1143 throw new ArrayIndexOutOfBoundsException();
1144 }
1145 if (fromIndex == toIndex) {
1146 return;
1147 }
1148
1149 final var n = toIndex - fromIndex;
1150
1151 int i;
1152 int j;
1153 int ir;
1154 int k;
1155 var jstack = -1;
1156 var l = 0;
1157 long a;
1158 final var istack = new int[NSTACK];
1159 ir = n - 1;
1160
1161 for (; ; ) {
1162 // Insertion sort when subarray is small enough
1163 if (ir - l < M) {
1164 for (j = l + 1; j <= ir; j++) {
1165 a = array[j + fromIndex];
1166 for (i = j - 1; i >= l; i--) {
1167 if (array[i + fromIndex] <= a) {
1168 break;
1169 }
1170 array[i + 1 + fromIndex] = array[i + fromIndex];
1171 }
1172 array[i + 1 + fromIndex] = a;
1173 }
1174 if (jstack < 0) {
1175 break;
1176 }
1177 // Pop stack and begin a new round of partitioning
1178 ir = istack[jstack--];
1179 l = istack[jstack--];
1180 } else {
1181 // Choose median of left, center, and right elements as
1182 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
1183 // <= a(ir)
1184 k = (l + ir) >> 1;
1185 swap(array, k + fromIndex, l + 1 + fromIndex);
1186 if (array[l + fromIndex] > array[ir + fromIndex]) {
1187 swap(array, l + fromIndex, ir + fromIndex);
1188 }
1189 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
1190 swap(array, l + 1 + fromIndex, ir + fromIndex);
1191 }
1192 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
1193 swap(array, l + fromIndex, l + 1 + fromIndex);
1194 }
1195 // Initialize pointers for partitioning
1196 i = l + 1;
1197 j = ir;
1198 // Partitioning element
1199 a = array[l + 1 + fromIndex];
1200 // Beginning of innermost loop
1201 for (; ; ) {
1202 // Scan up to find element > a
1203 do {
1204 i++;
1205 } while (array[i + fromIndex] < a);
1206 // Scan down to find element < a
1207 do {
1208 j--;
1209 } while (array[j + fromIndex] > a);
1210 // Pointers crossed. Partitioning complete
1211 if (j < i) {
1212 break;
1213 }
1214 // Exchange elements
1215 swap(array, i + fromIndex, j + fromIndex);
1216 // End of innermost loop
1217 }
1218 // Insert partitioning element
1219 array[l + 1 + fromIndex] = array[j + fromIndex];
1220 array[j + fromIndex] = a;
1221 jstack += 2;
1222 // NSTACK too small in sort
1223 if (jstack >= NSTACK) {
1224 throw new SortingException();
1225 }
1226 // Push pointers to larger subarray on stack; process smaller
1227 // subarray immediately
1228 if (ir - i + 1 >= j - l) {
1229 istack[jstack] = ir;
1230 istack[jstack - 1] = i;
1231 ir = j - 1;
1232 } else {
1233 istack[jstack] = j - 1;
1234 istack[jstack - 1] = l;
1235 l = i;
1236 }
1237 }
1238 }
1239 }
1240
1241 /**
1242 * Sorts provided array in ascending order so that {@code
1243 * array[i - 1] < array[i]} for any valid i.
1244 * This method modifies provided array so that
1245 * after execution of this method array elements are ordered.
1246 * An array containing the original indices where elements were
1247 * located is returned so that other arrays or collections can be kept
1248 * in the same order.
1249 *
1250 * @param array Array to be sorted. After execution of this method
1251 * elements in array between fromIndex (inclusive) and toIndex
1252 * (exclusive) are modified so that they are on ascending order.
1253 * @param fromIndex Index were sorting starts (inclusive).
1254 * @param toIndex Index were sorting stops (exclusive).
1255 * @return Array containing original location of elements that have been
1256 * sorted. Only elements between fromIndex (inclusive) and toIndex
1257 * (exclusive) are modified, the remaining ones are kept in natural
1258 * order.
1259 * @throws SortingException If for some reason sorting fails.
1260 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
1261 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1262 * {@code toIndex > array.length}.
1263 */
1264 @Override
1265 public int[] sortWithIndices(final long[] array, final int fromIndex, final int toIndex) throws SortingException {
1266
1267 if (fromIndex > toIndex) {
1268 throw new IllegalArgumentException();
1269 }
1270 if (fromIndex < 0 || toIndex > array.length) {
1271 throw new ArrayIndexOutOfBoundsException();
1272 }
1273
1274 final int[] indices = getInitialIndicesVector(array.length);
1275 if (fromIndex == toIndex) {
1276 return indices;
1277 }
1278
1279 final int n = toIndex - fromIndex;
1280
1281 int i;
1282 int j;
1283 int ir;
1284 int k;
1285 var jstack = -1;
1286 var l = 0;
1287 long a;
1288 int b;
1289 final var istack = new int[NSTACK];
1290 ir = n - 1;
1291
1292 for (; ; ) {
1293 // Insertion sort when subarray is small enough
1294 if (ir - l < M) {
1295 for (j = l + 1; j <= ir; j++) {
1296 a = array[j + fromIndex];
1297 b = indices[j + fromIndex];
1298 for (i = j - 1; i >= l; i--) {
1299 if (array[i + fromIndex] <= a) {
1300 break;
1301 }
1302 array[i + 1 + fromIndex] = array[i + fromIndex];
1303 indices[i + 1 + fromIndex] = indices[i + fromIndex];
1304 }
1305 array[i + 1 + fromIndex] = a;
1306 indices[i + 1 + fromIndex] = b;
1307 }
1308 if (jstack < 0) {
1309 break;
1310 }
1311 // Pop stack and begin a new round of partitioning
1312 ir = istack[jstack--];
1313 l = istack[jstack--];
1314 } else {
1315 // Choose median of left, center, and right elements as
1316 // partitioning element "a". Also rearrange so that a(l) <= a(l+1)
1317 // <= a(ir)
1318 k = (l + ir) >> 1;
1319 swap(array, k + fromIndex, l + 1 + fromIndex);
1320 swapIndices(indices, k + fromIndex, l + 1 + fromIndex);
1321 if (array[l + fromIndex] > array[ir + fromIndex]) {
1322 swap(array, l + fromIndex, ir + fromIndex);
1323 swapIndices(indices, l + fromIndex, ir + fromIndex);
1324 }
1325 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
1326 swap(array, l + 1 + fromIndex, ir + fromIndex);
1327 swapIndices(indices, l + 1 + fromIndex, ir + fromIndex);
1328 }
1329 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
1330 swap(array, l + fromIndex, l + 1 + fromIndex);
1331 swapIndices(indices, l + fromIndex, l + 1 + fromIndex);
1332 }
1333 // Initialize pointers for partitioning
1334 i = l + 1;
1335 j = ir;
1336 // Partitioning element
1337 a = array[l + 1 + fromIndex];
1338 b = indices[l + 1 + fromIndex];
1339 // Beginning of innermost loop
1340 for (; ; ) {
1341 // Scan up to find element > a
1342 do {
1343 i++;
1344 } while (array[i + fromIndex] < a);
1345 // Scan down to find element < a
1346 do {
1347 j--;
1348 } while (array[j + fromIndex] > a);
1349 // Pointers crossed. Partitioning complete
1350 if (j < i) {
1351 break;
1352 }
1353 // Exchange elements
1354 swap(array, i + fromIndex, j + fromIndex);
1355 swapIndices(indices, i + fromIndex, j + fromIndex);
1356 // End of innermost loop
1357 }
1358 // Insert partitioning element
1359 array[l + 1 + fromIndex] = array[j + fromIndex];
1360 array[j + fromIndex] = a;
1361 indices[l + 1 + fromIndex] = indices[j + fromIndex];
1362 indices[j + fromIndex] = b;
1363 jstack += 2;
1364 // NSTACK too small in sort
1365 if (jstack >= NSTACK) {
1366 throw new SortingException();
1367 }
1368 // Push pointers to larger subarray on stack; process smaller
1369 // subarray immediately
1370 if (ir - i + 1 >= j - l) {
1371 istack[jstack] = ir;
1372 istack[jstack - 1] = i;
1373 ir = j - 1;
1374 } else {
1375 istack[jstack] = j - 1;
1376 istack[jstack - 1] = l;
1377 l = i;
1378 }
1379 }
1380 }
1381
1382 return indices;
1383 }
1384
1385 /**
1386 * Swaps values in array of indices at locations posA and posB.
1387 *
1388 * @param indices array containing indices to be swapped.
1389 * @param posA Location to be swapped.
1390 * @param posB Location to be swapped.
1391 */
1392 private void swapIndices(final int[] indices, final int posA, final int posB) {
1393 final var value = indices[posA];
1394 indices[posA] = indices[posB];
1395 indices[posB] = value;
1396 }
1397 }