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 Shell 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. 422
27 * Knuth. D.E. 1997, Sorting and Searching, 3rd ed., vol. 3 of The Art of
28 * Computer Programming (Reading, MA: Addison-Wesley)
29 * Sedgewick, R. 1998. Algorithms in C, 3rd ed. (Reading, MA: Addison-
30 * Wesley), Chapter 11.
31 */
32 @SuppressWarnings("Duplicates")
33 public class ShellSorter<T> extends Sorter<T> {
34
35 /**
36 * Constant defining increment factor to be used internally.
37 */
38 private static final int INCREMENT_FACTOR = 3;
39
40 /**
41 * Constant defining minimum increment before stopping the sorting
42 * process.
43 */
44 private static final int MIN_INCREMENT = 1;
45
46 /**
47 * Sorts provided array in ascending order so that {@code
48 * array[i - 1] < array[i]} for any valid i.
49 * This method modifies provided array so that
50 * after execution of this method array elements are ordered.
51 *
52 * @param array Array to be sorted. After execution of this method
53 * elements in array between fromIndex (inclusive) and toIndex
54 * (exclusive) are modified so that they are on ascending order.
55 * @param fromIndex Index were sorting starts (inclusive).
56 * @param toIndex Index were sorting stops (exclusive).
57 * @param comparator Determines whether an element is greater or lower
58 * than another one.
59 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
60 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
61 * {@code toIndex > array.length}.
62 */
63 @Override
64 public void sort(final T[] array, final int fromIndex, final int toIndex, final Comparator<T> comparator) {
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 int j;
77 var inc = MIN_INCREMENT;
78 final var n = toIndex - fromIndex;
79
80 T v;
81
82 do {
83 inc *= INCREMENT_FACTOR;
84 inc++;
85 } while (inc <= n);
86
87 // Loop over the partial sorts
88 do {
89 inc /= INCREMENT_FACTOR;
90 // Outer loop of straight insertion
91 for (int i = inc; i < n; i++) {
92 v = array[i + fromIndex];
93 j = i;
94
95 // Inner loop of straight insertion
96 while (comparator.compare(array[j - inc + fromIndex], v) > 0) {
97 array[j + fromIndex] = array[j - inc + fromIndex];
98 j -= inc;
99 if (j < inc) {
100 break;
101 }
102 }
103 array[j + fromIndex] = v;
104 }
105 } while (inc > MIN_INCREMENT);
106 }
107
108 /**
109 * Sorts provided array in ascending order so that {@code
110 * array[i - 1] < array[i]} for any valid i.
111 * This method modifies provided array so that
112 * after execution of this method array elements are ordered.
113 * An array containing the original indices where elements were
114 * located is returned so that other arrays or collections can be kept
115 * in the same order.
116 *
117 * @param array Array to be sorted. After execution of this method
118 * elements in array between fromIndex (inclusive) and toIndex
119 * (exclusive) are modified so that they are on ascending order.
120 * @param fromIndex Index were sorting starts (inclusive).
121 * @param toIndex Index were sorting stops (exclusive).
122 * @param comparator Determines whether an element is greater or lower
123 * than another one.
124 * @return Array containing original location of elements that have been
125 * sorted. Only elements between fromIndex (inclusive) and toIndex
126 * (exclusive) are modified, the remaining ones are kept in natural
127 * order.
128 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
129 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
130 * {@code toIndex > array.length}.
131 */
132 @Override
133 public int[] sortWithIndices(final T[] array, final int fromIndex, final int toIndex,
134 final Comparator<T> comparator) {
135
136 if (fromIndex > toIndex) {
137 throw new IllegalArgumentException();
138 }
139 if (fromIndex < 0 || toIndex > array.length) {
140 throw new ArrayIndexOutOfBoundsException();
141 }
142
143 final int[] indices = getInitialIndicesVector(array.length);
144 if (fromIndex == toIndex) {
145 return indices;
146 }
147
148 int j;
149 int b;
150 var inc = MIN_INCREMENT;
151 final var n = toIndex - fromIndex;
152
153 T v;
154
155 do {
156 inc *= INCREMENT_FACTOR;
157 inc++;
158 } while (inc <= n);
159
160 // Loop over the partial sorts
161 do {
162 inc /= INCREMENT_FACTOR;
163 // Outer loop of straight insertion
164 for (int i = inc; i < n; i++) {
165 v = array[i + fromIndex];
166 b = indices[i + fromIndex];
167 j = i;
168
169 // Inner loop of straight insertion
170 while (comparator.compare(array[j - inc + fromIndex], v) > 0) {
171 array[j + fromIndex] = array[j - inc + fromIndex];
172 indices[j + fromIndex] = indices[j - inc + fromIndex];
173 j -= inc;
174 if (j < inc) {
175 break;
176 }
177 }
178 array[j + fromIndex] = v;
179 indices[j + fromIndex] = b;
180 }
181 } while (inc > MIN_INCREMENT);
182
183 return indices;
184 }
185
186 /**
187 * Returns sorting method of this class.
188 *
189 * @return Sorting method.
190 */
191 @Override
192 public SortingMethod getMethod() {
193 return SortingMethod.SHELL_SORTING_METHOD;
194 }
195
196 /**
197 * Sorts provided array in ascending order so that {@code
198 * array[i - 1] < array[i]} for any valid i.
199 * This method modifies provided array so that
200 * after execution of this method array elements are ordered.
201 *
202 * @param array Array to be sorted. After execution of this method
203 * elements in array between fromIndex (inclusive) and toIndex
204 * (exclusive) are modified so that they are on ascending order.
205 * @param fromIndex Index were sorting starts (inclusive).
206 * @param toIndex Index were sorting stops (exclusive).
207 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
208 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
209 * {@code toIndex > array.length}.
210 */
211 @Override
212 public void sort(final double[] array, final int fromIndex, final int toIndex) {
213
214 if (fromIndex > toIndex) {
215 throw new IllegalArgumentException();
216 }
217 if (fromIndex < 0 || toIndex > array.length) {
218 throw new ArrayIndexOutOfBoundsException();
219 }
220 if (fromIndex == toIndex) {
221 return;
222 }
223
224 int j;
225 var inc = MIN_INCREMENT;
226 final var n = toIndex - fromIndex;
227
228 double v;
229
230 do {
231 inc *= INCREMENT_FACTOR;
232 inc++;
233 } while (inc <= n);
234
235 // Loop over the partial sorts
236 do {
237 inc /= INCREMENT_FACTOR;
238 // Outer loop of straight insertion
239 for (int i = inc; i < n; i++) {
240 v = array[i + fromIndex];
241 j = i;
242
243 // Inner loop of straight insertion
244 while (array[j - inc + fromIndex] > v) {
245 array[j + fromIndex] = array[j - inc + fromIndex];
246 j -= inc;
247 if (j < inc) {
248 break;
249 }
250 }
251 array[j + fromIndex] = v;
252 }
253 } while (inc > MIN_INCREMENT);
254 }
255
256 /**
257 * Sorts provided array in ascending order so that {@code
258 * array[i - 1] < array[i]} for any valid i.
259 * This method modifies provided array so that
260 * after execution of this method array elements are ordered.
261 * An array containing the original indices where elements were
262 * located is returned so that other arrays or collections can be kept
263 * in the same order.
264 *
265 * @param array Array to be sorted. After execution of this method
266 * elements in array between fromIndex (inclusive) and toIndex
267 * (exclusive) are modified so that they are on ascending order.
268 * @param fromIndex Index were sorting starts (inclusive).
269 * @param toIndex Index were sorting stops (exclusive).
270 * @return Array containing original location of elements that have been
271 * sorted. Only elements between fromIndex (inclusive) and toIndex
272 * (exclusive) are modified, the remaining ones are kept in natural
273 * order.
274 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
275 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
276 * {@code toIndex > array.length}.
277 */
278 @Override
279 public int[] sortWithIndices(final double[] array, final int fromIndex, final int toIndex) {
280
281 if (fromIndex > toIndex) {
282 throw new IllegalArgumentException();
283 }
284 if (fromIndex < 0 || toIndex > array.length) {
285 throw new ArrayIndexOutOfBoundsException();
286 }
287
288 final int[] indices = getInitialIndicesVector(array.length);
289 if (fromIndex == toIndex) {
290 return indices;
291 }
292
293 int j;
294 int b;
295 var inc = MIN_INCREMENT;
296 final var n = toIndex - fromIndex;
297
298 double v;
299
300 do {
301 inc *= INCREMENT_FACTOR;
302 inc++;
303 } while (inc <= n);
304
305 // Loop over the partial sorts
306 do {
307 inc /= INCREMENT_FACTOR;
308 // Outer loop of straight insertion
309 for (int i = inc; i < n; i++) {
310 v = array[i + fromIndex];
311 b = indices[i + fromIndex];
312 j = i;
313
314 // Inner loop of straight insertion
315 while (array[j - inc + fromIndex] > v) {
316 array[j + fromIndex] = array[j - inc + fromIndex];
317 indices[j + fromIndex] = indices[j - inc + fromIndex];
318 j -= inc;
319 if (j < inc) {
320 break;
321 }
322 }
323 array[j + fromIndex] = v;
324 indices[j + fromIndex] = b;
325 }
326 } while (inc > MIN_INCREMENT);
327
328 return indices;
329 }
330
331 /**
332 * Sorts provided array in ascending order so that {@code
333 * array[i - 1] < array[i]} for any valid i.
334 * This method modifies provided array so that
335 * after execution of this method array elements are ordered.
336 *
337 * @param array Array to be sorted. After execution of this method
338 * elements in array between fromIndex (inclusive) and toIndex
339 * (exclusive) are modified so that they are on ascending order.
340 * @param fromIndex Index were sorting starts (inclusive).
341 * @param toIndex Index were sorting stops (exclusive).
342 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
343 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
344 * {@code toIndex > array.length}.
345 */
346 @Override
347 public void sort(final float[] array, final int fromIndex, final int toIndex) {
348
349 if (fromIndex > toIndex) {
350 throw new IllegalArgumentException();
351 }
352 if (fromIndex < 0 || toIndex > array.length) {
353 throw new ArrayIndexOutOfBoundsException();
354 }
355 if (fromIndex == toIndex) {
356 return;
357 }
358
359 int j;
360 var inc = MIN_INCREMENT;
361 final var n = toIndex - fromIndex;
362
363 float v;
364
365 do {
366 inc *= INCREMENT_FACTOR;
367 inc++;
368 } while (inc <= n);
369
370 // Loop over the partial sorts
371 do {
372 inc /= INCREMENT_FACTOR;
373 // Outer loop of straight insertion
374 for (int i = inc; i < n; i++) {
375 v = array[i + fromIndex];
376 j = i;
377
378 // Inner loop of straight insertion
379 while (array[j - inc + fromIndex] > v) {
380 array[j + fromIndex] = array[j - inc + fromIndex];
381 j -= inc;
382 if (j < inc) {
383 break;
384 }
385 }
386 array[j + fromIndex] = v;
387 }
388 } while (inc > MIN_INCREMENT);
389 }
390
391 /**
392 * Sorts provided array in ascending order so that {@code
393 * array[i - 1] < array[i]} for any valid i.
394 * This method modifies provided array so that
395 * after execution of this method array elements are ordered.
396 * An array containing the original indices where elements were
397 * located is returned so that other arrays or collections can be kept
398 * in the same order.
399 *
400 * @param array Array to be sorted. After execution of this method
401 * elements in array between fromIndex (inclusive) and toIndex
402 * (exclusive) are modified so that they are on ascending order.
403 * @param fromIndex Index were sorting starts (inclusive).
404 * @param toIndex Index were sorting stops (exclusive).
405 * @return Array containing original location of elements that have been
406 * sorted. Only elements between fromIndex (inclusive) and toIndex
407 * (exclusive) are modified, the remaining ones are kept in natural
408 * order.
409 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
410 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
411 * {@code toIndex > array.length}.
412 */
413 @Override
414 public int[] sortWithIndices(final float[] array, final int fromIndex, final int toIndex) {
415
416 if (fromIndex > toIndex) {
417 throw new IllegalArgumentException();
418 }
419 if (fromIndex < 0 || toIndex > array.length) {
420 throw new ArrayIndexOutOfBoundsException();
421 }
422
423 final var indices = getInitialIndicesVector(array.length);
424 if (fromIndex == toIndex) {
425 return indices;
426 }
427
428 int j;
429 int b;
430 var inc = MIN_INCREMENT;
431 final var n = toIndex - fromIndex;
432
433 float v;
434
435 do {
436 inc *= INCREMENT_FACTOR;
437 inc++;
438 } while (inc <= n);
439
440 // Loop over the partial sorts
441 do {
442 inc /= INCREMENT_FACTOR;
443 // Outer loop of straight insertion
444 for (int i = inc; i < n; i++) {
445 v = array[i + fromIndex];
446 b = indices[i + fromIndex];
447 j = i;
448
449 // Inner loop of straight insertion
450 while (array[j - inc + fromIndex] > v) {
451 array[j + fromIndex] = array[j - inc + fromIndex];
452 indices[j + fromIndex] = indices[j - inc + fromIndex];
453 j -= inc;
454 if (j < inc) {
455 break;
456 }
457 }
458 array[j + fromIndex] = v;
459 indices[j + fromIndex] = b;
460 }
461 } while (inc > MIN_INCREMENT);
462
463 return indices;
464 }
465
466 /**
467 * Sorts provided array in ascending order so that {@code
468 * array[i - 1] < array[i]} for any valid i.
469 * This method modifies provided array so that
470 * after execution of this method array elements are ordered.
471 *
472 * @param array Array to be sorted. After execution of this method
473 * elements in array between fromIndex (inclusive) and toIndex
474 * (exclusive) are modified so that they are on ascending order.
475 * @param fromIndex Index were sorting starts (inclusive).
476 * @param toIndex Index were sorting stops (exclusive).
477 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
478 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
479 * {@code toIndex > array.length}.
480 */
481 @Override
482 public void sort(final int[] array, final int fromIndex, final int toIndex) {
483
484 if (fromIndex > toIndex) {
485 throw new IllegalArgumentException();
486 }
487 if (fromIndex < 0 || toIndex > array.length) {
488 throw new ArrayIndexOutOfBoundsException();
489 }
490 if (fromIndex == toIndex) {
491 return;
492 }
493
494 int j;
495 var inc = MIN_INCREMENT;
496 final var n = toIndex - fromIndex;
497
498 int v;
499
500 do {
501 inc *= INCREMENT_FACTOR;
502 inc++;
503 } while (inc <= n);
504
505 // Loop over the partial sorts
506 do {
507 inc /= INCREMENT_FACTOR;
508 // Outer loop of straight insertion
509 for (int i = inc; i < n; i++) {
510 v = array[i + fromIndex];
511 j = i;
512
513 // Inner loop of straight insertion
514 while (array[j - inc + fromIndex] > v) {
515 array[j + fromIndex] = array[j - inc + fromIndex];
516 j -= inc;
517 if (j < inc) {
518 break;
519 }
520 }
521 array[j + fromIndex] = v;
522 }
523 } while (inc > MIN_INCREMENT);
524 }
525
526 /**
527 * Sorts provided array in ascending order so that {@code
528 * array[i - 1] < array[i]} for any valid i.
529 * This method modifies provided array so that
530 * after execution of this method array elements are ordered.
531 * An array containing the original indices where elements were
532 * located is returned so that other arrays or collections can be kept
533 * in the same order.
534 *
535 * @param array Array to be sorted. After execution of this method
536 * elements in array between fromIndex (inclusive) and toIndex
537 * (exclusive) are modified so that they are on ascending order.
538 * @param fromIndex Index were sorting starts (inclusive).
539 * @param toIndex Index were sorting stops (exclusive).
540 * @return Array containing original location of elements that have been
541 * sorted. Only elements between fromIndex (inclusive) and toIndex
542 * (exclusive) are modified, the remaining ones are kept in natural
543 * order.
544 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
545 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
546 * {@code toIndex > array.length}.
547 */
548 @Override
549 public int[] sortWithIndices(final int[] array, final int fromIndex, final int toIndex) {
550
551 if (fromIndex > toIndex) {
552 throw new IllegalArgumentException();
553 }
554 if (fromIndex < 0 || toIndex > array.length) {
555 throw new ArrayIndexOutOfBoundsException();
556 }
557
558 final int[] indices = getInitialIndicesVector(array.length);
559 if (fromIndex == toIndex) {
560 return indices;
561 }
562
563 int j;
564 int b;
565 var inc = MIN_INCREMENT;
566 final var n = toIndex - fromIndex;
567
568 int v;
569
570 do {
571 inc *= INCREMENT_FACTOR;
572 inc++;
573 } while (inc <= n);
574
575 // Loop over the partial sorts
576 do {
577 inc /= INCREMENT_FACTOR;
578 // Outer loop of straight insertion
579 for (int i = inc; i < n; i++) {
580 v = array[i + fromIndex];
581 b = indices[i + fromIndex];
582 j = i;
583
584 // Inner loop of straight insertion
585 while (array[j - inc + fromIndex] > v) {
586 array[j + fromIndex] = array[j - inc + fromIndex];
587 indices[j + fromIndex] = indices[j - inc + fromIndex];
588 j -= inc;
589 if (j < inc) {
590 break;
591 }
592 }
593 array[j + fromIndex] = v;
594 indices[j + fromIndex] = b;
595 }
596 } while (inc > MIN_INCREMENT);
597
598 return indices;
599 }
600
601 /**
602 * Sorts provided array in ascending order so that {@code
603 * array[i - 1] < array[i]} for any valid i.
604 * This method modifies provided array so that
605 * after execution of this method array elements are ordered.
606 *
607 * @param array Array to be sorted. After execution of this method
608 * elements in array between fromIndex (inclusive) and toIndex
609 * (exclusive) are modified so that they are on ascending order.
610 * @param fromIndex Index were sorting starts (inclusive).
611 * @param toIndex Index were sorting stops (exclusive).
612 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
613 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
614 * {@code toIndex > array.length}.
615 */
616 @Override
617 public void sort(final long[] array, final int fromIndex, final int toIndex) {
618
619 if (fromIndex > toIndex) {
620 throw new IllegalArgumentException();
621 }
622 if (fromIndex < 0 || toIndex > array.length) {
623 throw new ArrayIndexOutOfBoundsException();
624 }
625 if (fromIndex == toIndex) {
626 return;
627 }
628
629 int j;
630 var inc = MIN_INCREMENT;
631 final var n = toIndex - fromIndex;
632
633 long v;
634
635 do {
636 inc *= INCREMENT_FACTOR;
637 inc++;
638 } while (inc <= n);
639
640 // Loop over the partial sorts
641 do {
642 inc /= INCREMENT_FACTOR;
643 // Outer loop of straight insertion
644 for (int i = inc; i < n; i++) {
645 v = array[i + fromIndex];
646 j = i;
647
648 // Inner loop of straight insertion
649 while (array[j - inc + fromIndex] > v) {
650 array[j + fromIndex] = array[j - inc + fromIndex];
651 j -= inc;
652 if (j < inc) {
653 break;
654 }
655 }
656 array[j + fromIndex] = v;
657 }
658 } while (inc > MIN_INCREMENT);
659 }
660
661 /**
662 * Sorts provided array in ascending order so that {@code
663 * array[i - 1] < array[i]} for any valid i.
664 * This method modifies provided array so that
665 * after execution of this method array elements are ordered.
666 * An array containing the original indices where elements were
667 * located is returned so that other arrays or collections can be kept
668 * in the same order.
669 *
670 * @param array Array to be sorted. After execution of this method
671 * elements in array between fromIndex (inclusive) and toIndex
672 * (exclusive) are modified so that they are on ascending order.
673 * @param fromIndex Index were sorting starts (inclusive).
674 * @param toIndex Index were sorting stops (exclusive).
675 * @return Array containing original location of elements that have been
676 * sorted. Only elements between fromIndex (inclusive) and toIndex
677 * (exclusive) are modified, the remaining ones are kept in natural
678 * order.
679 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
680 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
681 * {@code toIndex > array.length}.
682 */
683 @Override
684 public int[] sortWithIndices(final long[] array, final int fromIndex, final int toIndex) {
685
686 if (fromIndex > toIndex) {
687 throw new IllegalArgumentException();
688 }
689 if (fromIndex < 0 || toIndex > array.length) {
690 throw new ArrayIndexOutOfBoundsException();
691 }
692
693 final int[] indices = getInitialIndicesVector(array.length);
694 if (fromIndex == toIndex) {
695 return indices;
696 }
697
698 int j;
699 int b;
700 var inc = MIN_INCREMENT;
701 final var n = toIndex - fromIndex;
702
703 long v;
704
705 do {
706 inc *= INCREMENT_FACTOR;
707 inc++;
708 } while (inc <= n);
709
710 // Loop over the partial sorts
711 do {
712 inc /= INCREMENT_FACTOR;
713 // Outer loop of straight insertion
714 for (int i = inc; i < n; i++) {
715 v = array[i + fromIndex];
716 b = indices[i + fromIndex];
717 j = i;
718
719 // Inner loop of straight insertion
720 while (array[j - inc + fromIndex] > v) {
721 array[j + fromIndex] = array[j - inc + fromIndex];
722 indices[j + fromIndex] = indices[j - inc + fromIndex];
723 j -= inc;
724 if (j < inc) {
725 break;
726 }
727 }
728 array[j + fromIndex] = v;
729 indices[j + fromIndex] = b;
730 }
731 } while (inc > MIN_INCREMENT);
732
733 return indices;
734 }
735 }