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 any of the
22 * available methods.
23 *
24 * @param <T> Type of instances being sorted.
25 */
26 @SuppressWarnings({"WeakerAccess", "Duplicates"})
27 public abstract class Sorter<T> {
28
29 /**
30 * Default method to be used for sorting if none is provided.
31 */
32 public static final SortingMethod DEFAULT_SORTING_METHOD = SortingMethod.SYSTEM_SORTING_METHOD;
33
34 /**
35 * Sorts provided array in ascending order so that {@code
36 * array[i - 1] < array[i]} for any valid i.
37 * This method modifies provided array so that
38 * after execution of this method array elements are ordered.
39 *
40 * @param array Array to be sorted. After execution of this method
41 * elements in array between fromIndex (inclusive) and toIndex
42 * (exclusive) are modified so that they are on ascending order.
43 * @param fromIndex Index were sorting starts (inclusive).
44 * @param toIndex Index were sorting stops (exclusive).
45 * @param comparator Determines whether an element is greater or lower
46 * than another one.
47 * @throws SortingException If for some reason sorting fails.
48 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
49 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
50 * {@code toIndex > array.length}.
51 */
52 public abstract void sort(final T[] array, final int fromIndex, final int toIndex, final Comparator<T> comparator)
53 throws SortingException;
54
55 /**
56 * Sorts provided array in ascending order so that {@code
57 * array[i - 1] < array[i]} for any valid i.
58 * This method modifies provided array so that
59 * after execution of this method array elements are ordered.
60 * An array containing the original indices where elements were
61 * located is returned so that other arrays or collections can be kept
62 * in the same order.
63 *
64 * @param array Array to be sorted. After execution of this method
65 * elements in array between fromIndex (inclusive) and toIndex
66 * (exclusive) are modified so that they are on ascending order.
67 * @param fromIndex Index were sorting starts (inclusive).
68 * @param toIndex Index were sorting stops (exclusive).
69 * @param comparator Determines whether an element is greater or lower
70 * than another one.
71 * @return Array containing original location of elements that have been
72 * sorted. Only elements between fromIndex (inclusive) and toIndex
73 * (exclusive) are modified, the remaining ones are kept in natural
74 * order.
75 * @throws SortingException If for some reason sorting fails.
76 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
77 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
78 * {@code toIndex > array.length}.
79 */
80 public abstract int[] sortWithIndices(final T[] array, final int fromIndex, final int toIndex,
81 final Comparator<T> comparator) throws SortingException;
82
83 /**
84 * Sorts provided array in ascending order so that {@code
85 * array[i - 1] < array[i]} for any valid i.
86 * This method modifies provided array so that
87 * after execution of this method array elements are ordered.
88 *
89 * @param array Array to be sorted. After execution of this method
90 * elements in array between fromIndex (inclusive) and toIndex
91 * (exclusive) are modified so that they are on ascending order.
92 * @param fromIndex Index were sorting starts (inclusive).
93 * @param toIndex Index were sorting stops (exclusive).
94 * @throws SortingException If for some reason sorting fails.
95 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
96 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
97 * {@code toIndex > array.length}.
98 */
99 public abstract void sort(final double[] array, final int fromIndex, final int toIndex)
100 throws SortingException;
101
102 /**
103 * Sorts provided array in ascending order so that {@code
104 * array[i - 1] < array[i]} for any valid i.
105 * This method modifies provided array so that
106 * after execution of this method array elements are ordered.
107 * An array containing the original indices where elements were
108 * located is returned so that other arrays or collections can be kept
109 * in the same order.
110 *
111 * @param array Array to be sorted. After execution of this method
112 * elements in array between fromIndex (inclusive) and toIndex
113 * (exclusive) are modified so that they are on ascending order.
114 * @param fromIndex Index were sorting starts (inclusive).
115 * @param toIndex Index were sorting stops (exclusive).
116 * @return Array containing original location of elements that have been
117 * sorted. Only elements between fromIndex (inclusive) and toIndex
118 * (exclusive) are modified, the remaining ones are kept in natural
119 * order.
120 * @throws SortingException If for some reason sorting fails.
121 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
122 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
123 * {@code toIndex > array.length}.
124 */
125 public abstract int[] sortWithIndices(final double[] array, final int fromIndex, final int toIndex)
126 throws SortingException;
127
128 /**
129 * Sorts provided array in ascending order so that {@code
130 * array[i - 1] < array[i]} for any valid i.
131 * This method modifies provided array so that
132 * after execution of this method array elements are ordered.
133 *
134 * @param array Array to be sorted. After execution of this method
135 * elements in array between fromIndex (inclusive) and toIndex
136 * (exclusive) are modified so that they are on ascending order.
137 * @param fromIndex Index were sorting starts (inclusive).
138 * @param toIndex Index were sorting stops (exclusive).
139 * @throws SortingException If for some reason sorting fails.
140 * @throws IllegalArgumentException If {@code fromIndex > toIndex}
141 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
142 * {@code toIndex > array.length}.
143 */
144 public abstract void sort(final float[] array, final int fromIndex, final int toIndex) throws SortingException;
145
146 /**
147 * Sorts provided array in ascending order so that {@code
148 * array[i - 1] < array[i]} for any valid i.
149 * This method modifies provided array so that
150 * after execution of this method array elements are ordered.
151 * An array containing the original indices where elements were
152 * located is returned so that other arrays or collections can be kept
153 * in the same order.
154 *
155 * @param array Array to be sorted. After execution of this method
156 * elements in array between fromIndex (inclusive) and toIndex
157 * (exclusive) are modified so that they are on ascending order.
158 * @param fromIndex Index were sorting starts (inclusive).
159 * @param toIndex Index were sorting stops (exclusive).
160 * @return Array containing original location of elements that have been
161 * sorted. Only elements between fromIndex (inclusive) and toIndex
162 * (exclusive) are modified, the remaining ones are kept in natural
163 * order.
164 * @throws SortingException If for some reason sorting fails.
165 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
166 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
167 * {@code toIndex > array.length}.
168 */
169 public abstract int[] sortWithIndices(final float[] array, final int fromIndex, final int toIndex)
170 throws SortingException;
171
172 /**
173 * Sorts provided array in ascending order so that {@code
174 * array[i - 1] < array[i]} for any valid i.
175 * This method modifies provided array so that
176 * after execution of this method array elements are ordered.
177 *
178 * @param array Array to be sorted. After execution of this method
179 * elements in array between fromIndex (inclusive) and toIndex
180 * (exclusive) are modified so that they are on ascending order.
181 * @param fromIndex Index were sorting starts (inclusive).
182 * @param toIndex Index were sorting stops (exclusive).
183 * @throws SortingException If for some reason sorting fails.
184 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
185 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
186 * {@code toIndex > array.length}.
187 */
188 public abstract void sort(final int[] array, final int fromIndex, final int toIndex) throws SortingException;
189
190 /**
191 * Sorts provided array in ascending order so that {@code
192 * array[i - 1] < array[i]} for any valid i.
193 * This method modifies provided array so that
194 * after execution of this method array elements are ordered.
195 * An array containing the original indices where elements were
196 * located is returned so that other arrays or collections can be kept
197 * in the same order.
198 *
199 * @param array Array to be sorted. After execution of this method
200 * elements in array between fromIndex (inclusive) and toIndex
201 * (exclusive) are modified so that they are on ascending order.
202 * @param fromIndex Index were sorting starts (inclusive).
203 * @param toIndex Index were sorting stops (exclusive).
204 * @return Array containing original location of elements that have been
205 * sorted. Only elements between fromIndex (inclusive) and toIndex
206 * (exclusive) are modified, the remaining ones are kept in natural
207 * order.
208 * @throws SortingException If for some reason sorting fails.
209 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
210 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
211 * {@code toIndex > array.length}.
212 */
213 public abstract int[] sortWithIndices(final int[] array, final int fromIndex, final int toIndex)
214 throws SortingException;
215
216 /**
217 * Sorts provided array in ascending order so that {@code
218 * array[i - 1] < array[i]} for any valid i.
219 * This method modifies provided array so that
220 * after execution of this method array elements are ordered.
221 *
222 * @param array Array to be sorted. After execution of this method
223 * elements in array between fromIndex (inclusive) and toIndex
224 * (exclusive) are modified so that they are on ascending order.
225 * @param fromIndex Index were sorting starts (inclusive).
226 * @param toIndex Index were sorting stops (exclusive).
227 * @throws SortingException If for some reason sorting fails.
228 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
229 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
230 * {@code toIndex > array.length}.
231 */
232 public abstract void sort(final long[] array, final int fromIndex, final int toIndex) throws SortingException;
233
234 /**
235 * Sorts provided array in ascending order so that {@code
236 * array[i - 1] < array[i]} for any valid i.
237 * This method modifies provided array so that
238 * after execution of this method array elements are ordered.
239 * An array containing the original indices where elements were
240 * located is returned so that other arrays or collections can be kept
241 * in the same order.
242 *
243 * @param array Array to be sorted. After execution of this method
244 * elements in array between fromIndex (inclusive) and toIndex
245 * (exclusive) are modified so that they are on ascending order.
246 * @param fromIndex Index were sorting starts (inclusive).
247 * @param toIndex Index were sorting stops (exclusive).
248 * @return Array containing original location of elements that have been
249 * sorted. Only elements between fromIndex (inclusive) and toIndex
250 * (exclusive) are modified, the remaining ones are kept in natural
251 * order.
252 * @throws SortingException If for some reason sorting fails.
253 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
254 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
255 * {@code toIndex > array.length}.
256 */
257 public abstract int[] sortWithIndices(final long[] array, final int fromIndex, final int toIndex)
258 throws SortingException;
259
260 /**
261 * Sorts provided array of {@link Comparable} in ascending order so that
262 * {@code array[i - 1] < array[i]} for any valid i.
263 * This method modifies provided array so that
264 * after execution of this method array elements are ordered.
265 *
266 * @param array Array to be sorted. After execution of this method
267 * elements in array between fromIndex (inclusive) and toIndex
268 * (exclusive) are modified so that they are on ascending order.
269 * @param fromIndex Index were sorting starts (inclusive).
270 * @param toIndex Index were sorting stops (exclusive).
271 * @throws SortingException If for some reason sorting fails.
272 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
273 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
274 * {@code toIndex > array.length}.
275 */
276 @SuppressWarnings("unchecked")
277 public void sort(final Comparable<T>[] array, final int fromIndex, final int toIndex) throws SortingException {
278 sort((T[]) array, fromIndex, toIndex, (t1, t2) -> {
279 final var t1b = (Comparable<T>) t1;
280 return t1b.compareTo(t2);
281 });
282 }
283
284 /**
285 * Sorts provided array of {@link Comparable} in ascending order so that
286 * {@code array[i - 1] < array[i]} for any valid i.
287 * This method modifies provided array so that
288 * after execution of this method array elements are ordered.
289 *
290 * @param array Array to be sorted. After execution of this method
291 * all elements in array are modified so that they are on ascending
292 * order.
293 * @throws SortingException If for some reason sorting fails.
294 */
295 public void sort(final Comparable<T>[] array) throws SortingException {
296 sort(array, 0, array.length);
297 }
298
299 /**
300 * Sorts provided array in ascending order so that {@code
301 * array[i - 1] < array[i]} for any valid i.
302 * This method modifies provided array so that
303 * after execution of this method array elements are ordered.
304 *
305 * @param array Array to be sorted. After execution of this method
306 * all elements in array are modified so that they are on ascending
307 * order.
308 * @param comparator Determines whether an element is greater or lower
309 * than another one.
310 * @throws SortingException If for some reason sorting fails.
311 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
312 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
313 * {@code toIndex > array.length}.
314 */
315 public void sort(final T[] array, final Comparator<T> comparator) throws SortingException {
316 sort(array, 0, array.length, comparator);
317 }
318
319 /**
320 * Sorts provided array in ascending order so that {@code
321 * array[i - 1] < array[i]} for any valid i.
322 * This method modifies provided array so that
323 * after execution of this method array elements are ordered.
324 *
325 * @param array Array to be sorted. After execution of this method
326 * all elements in array are modified so that they are on ascending
327 * order.
328 * @throws SortingException If for some reason sorting fails.
329 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
330 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
331 * {@code toIndex > array.length}.
332 */
333 public void sort(final double[] array) throws SortingException {
334 sort(array, 0, array.length);
335 }
336
337 /**
338 * Sorts provided array in ascending order so that {@code
339 * array[i - 1] < array[i]} for any valid i.
340 * This method modifies provided array so that
341 * after execution of this method array elements are ordered.
342 *
343 * @param array Array to be sorted. After execution of this method
344 * all elements in array are modified so that they are on ascending
345 * order.
346 * @throws SortingException If for some reason sorting fails.
347 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
348 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
349 * {@code toIndex > array.length}.
350 */
351 public void sort(final float[] array) throws SortingException {
352 sort(array, 0, array.length);
353 }
354
355 /**
356 * Sorts provided array in ascending order so that {@code
357 * array[i - 1] < array[i]} for any valid i.
358 * This method modifies provided array so that
359 * after execution of this method array elements are ordered.
360 *
361 * @param array Array to be sorted. After execution of this method
362 * all elements in array are modified so that they are on ascending
363 * order.
364 * @throws SortingException If for some reason sorting fails.
365 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
366 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
367 * {@code toIndex > array.length}.
368 */
369 public void sort(final int[] array) throws SortingException {
370 sort(array, 0, array.length);
371 }
372
373 /**
374 * Sorts provided array in ascending order so that {@code
375 * array[i - 1] < array[i]} for any valid i.
376 * This method modifies provided array so that
377 * after execution of this method array elements are ordered.
378 *
379 * @param array Array to be sorted. After execution of this method
380 * all elements in array are modified so that they are on ascending
381 * order.
382 * @throws SortingException If for some reason sorting fails.
383 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
384 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
385 * {@code toIndex > array.length}.
386 */
387 public void sort(final long[] array) throws SortingException {
388 sort(array, 0, array.length);
389 }
390
391
392 /**
393 * Sorts provided array of {@link Comparable} in ascending order so that
394 * {@code array[i - 1] < array[i]} for any valid i.
395 * This method modifies provided array so that
396 * after execution of this method array elements are ordered.
397 * An array containing the original indices where elements were
398 * located is returned so that other arrays or collections can be kept
399 * in the same order.
400 *
401 * @param array Array to be sorted. After execution of this method
402 * elements in array between fromIndex (inclusive) and toIndex
403 * (exclusive) are modified so that they are on ascending order.
404 * @param fromIndex Index were sorting starts (inclusive).
405 * @param toIndex Index were sorting stops (exclusive).
406 * @return Array containing original location of elements that have been
407 * sorted. Only elements between fromIndex (inclusive) and toIndex
408 * (exclusive) are modified, the remaining ones are kept in natural
409 * order.
410 * @throws SortingException If for some reason sorting fails.
411 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
412 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
413 * {@code toIndex > array.length}.
414 */
415 @SuppressWarnings("unchecked")
416 public int[] sortWithIndices(final Comparable<T>[] array, final int fromIndex, final int toIndex)
417 throws SortingException {
418 return sortWithIndices((T[]) array, fromIndex, toIndex, (t1, t2) -> {
419 final var t1b = (Comparable<T>) t1;
420 return t1b.compareTo(t2);
421 });
422 }
423
424 /**
425 * Sorts provided array of {@link Comparable} in ascending order so that
426 * {@code array[i - 1] < array[i]} for any valid i.
427 * This method modifies provided array so that
428 * after execution of this method array elements are ordered.
429 * An array containing the original indices where elements were
430 * located is returned so that other arrays or collections can be kept
431 * in the same order.
432 *
433 * @param array Array to be sorted. After execution of this method
434 * all elements in array are modified so that they are on ascending
435 * order.
436 * @return Array containing original location of elements that have been
437 * sorted.
438 * @throws SortingException If for some reason sorting fails.
439 */
440 public int[] sortWithIndices(final Comparable<T>[] array) throws SortingException {
441 return sortWithIndices(array, 0, array.length);
442 }
443
444 /**
445 * Sorts provided array of {@link Comparable} in ascending order so that
446 * {@code array[i - 1] < array[i]} for any valid i.
447 * This method modifies provided array so that
448 * after execution of this method array elements are ordered.
449 * An array containing the original indices where elements were
450 * located is returned so that other arrays or collections can be kept
451 * in the same order.
452 *
453 * @param array Array to be sorted. After execution of this method
454 * all elements in array are modified so that they are on ascending
455 * order.
456 * @param comparator Determines whether an element is greater or lower
457 * than another one.
458 * @return Array containing original location of elements that have been
459 * sorted.
460 * @throws SortingException If for some reason sorting fails.
461 */
462 public int[] sortWithIndices(final T[] array, final Comparator<T> comparator) throws SortingException {
463 return sortWithIndices(array, 0, array.length, comparator);
464 }
465
466 /**
467 * Sorts provided array of {@link Comparable} in ascending order so that
468 * {@code 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 * An array containing the original indices where elements were
472 * located is returned so that other arrays or collections can be kept
473 * in the same order.
474 *
475 * @param array Array to be sorted. After execution of this method
476 * all elements in array are modified so that they are on ascending
477 * order.
478 * @return Array containing original location of elements that have been
479 * sorted.
480 * @throws SortingException If for some reason sorting fails.
481 */
482 public int[] sortWithIndices(final double[] array) throws SortingException {
483 return sortWithIndices(array, 0, array.length);
484 }
485
486 /**
487 * Sorts provided array of {@link Comparable} in ascending order so that
488 * {@code array[i - 1] < array[i]} for any valid i.
489 * This method modifies provided array so that
490 * after execution of this method array elements are ordered.
491 * An array containing the original indices where elements were
492 * located is returned so that other arrays or collections can be kept
493 * in the same order.
494 *
495 * @param array Array to be sorted. After execution of this method
496 * all elements in array are modified so that they are on ascending
497 * order.
498 * @return Array containing original location of elements that have been
499 * sorted.
500 * @throws SortingException If for some reason sorting fails.
501 */
502 public int[] sortWithIndices(final float[] array) throws SortingException {
503 return sortWithIndices(array, 0, array.length);
504 }
505
506 /**
507 * Sorts provided array of {@link Comparable} in ascending order so that
508 * {@code array[i - 1] < array[i]} for any valid i.
509 * This method modifies provided array so that
510 * after execution of this method array elements are ordered.
511 * An array containing the original indices where elements were
512 * located is returned so that other arrays or collections can be kept
513 * in the same order.
514 *
515 * @param array Array to be sorted. After execution of this method
516 * all elements in array are modified so that they are on ascending
517 * order.
518 * @return Array containing original location of elements that have been
519 * sorted.
520 * @throws SortingException If for some reason sorting fails.
521 */
522 public int[] sortWithIndices(final int[] array) throws SortingException {
523 return sortWithIndices(array, 0, array.length);
524 }
525
526 /**
527 * Sorts provided array of {@link Comparable} in ascending order so that
528 * {@code 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 * all elements in array are modified so that they are on ascending
537 * order.
538 * @return Array containing original location of elements that have been
539 * sorted.
540 * @throws SortingException If for some reason sorting fails.
541 */
542 public int[] sortWithIndices(final long[] array) throws SortingException {
543 return sortWithIndices(array, 0, array.length);
544 }
545
546 /**
547 * Returns the k-th sorted element in provided array of {@link Comparable}.
548 * Selecting an element is usually faster than sorting the whole
549 * array, and for that reason, when only a few sorted elements are
550 * required, this method should be used instead of sort.
551 * Because array is passed by reference, after executing this method
552 * array is modified so that in k location it contains the k-th sorted
553 * elements and on locations array[0] ... array[k-1] contains unsorted
554 * elements smaller than sorted element array[k], and on locations
555 * array[k+1] ... array[length-1] contains unsorted elements greater
556 * than sorted element array[k].
557 *
558 * @param k Position of sorted element to be retrieved.
559 * @param array Array to be used for retrieving k-th sorted element.
560 * Provided array is passed by reference and modified upon execution of
561 * this method so that k-th location contains k-th sorted element, and
562 * array[0] ... array[k-1] contains unsorted elements smaller than
563 * sorted element array[k] and array[k+1] ... array[length-1] contains
564 * elements greater than sorted element array[k]
565 * @return The k-th sorted element in provided array
566 * @throws IllegalArgumentException if k < array.length
567 */
568 public T select(final int k, final Comparable<T>[] array) {
569 return select(k, array, 0, array.length);
570 }
571
572 /**
573 * Returns the k-th sorted element in provided array of {@link Comparable}
574 * starting at fromIndex and finishing at toIndex, elements outside this
575 * range are ignored.
576 * Selecting an element is usually faster than sorting the whole
577 * array, and for that reason, when only a few sorted elements are
578 * required, this method should be used instead of sort.
579 * Because array is passed by reference, after executing this method
580 * array is modified so that in k location it contains the k-th sorted
581 * elements and on locations array[fromIndex] ... array[k-1 + fromIndex]
582 * contains unsorted elements smaller than sorted element
583 * array[k + fromIndex], and on locations
584 * array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted
585 * elements greater than sorted element array[k + fromIndex].
586 *
587 * @param k Position of sorted element to be retrieved.
588 * @param array Array to be used for retrieving k-th sorted element.
589 * Provided array is passed by reference and modified upon execution of
590 * this method so that k-th location contains k-th sorted element, and
591 * array[fromIndex] ... array[k-1 + fromIndex] contains unsorted
592 * elements smaller than sorted element array[k + fromIndex] and
593 * array[k+1 + fromIndex] ... array[toIndex-1] contains elements
594 * greater than sorted element array[k].
595 * @param fromIndex Index were sorting starts (inclusive).
596 * @param toIndex Index were sorting stops (exclusive).
597 * @return The k-th sorted element in provided array.
598 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
599 * fromIndex < toIndex.
600 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
601 * outside array boundaries.
602 */
603 @SuppressWarnings("unchecked")
604 public T select(final int k, final Comparable<T>[] array, final int fromIndex, final int toIndex) {
605 return select(k, (T[]) array, fromIndex, toIndex, (t1, t2) -> {
606 final var t1b = (Comparable<T>) t1;
607 return t1b.compareTo(t2);
608 });
609 }
610
611 /**
612 * Returns the k-th sorted element in provided array.
613 * Selecting an element is usually faster than sorting the whole
614 * array, and for that reason, when only a few sorted elements are
615 * required, this method should be used instead of sort.
616 * Because array is passed by reference, after executing this method
617 * array is modified so that in k location it contains the k-th sorted
618 * elements and on locations array[0] ... array[k-1] contains unsorted
619 * elements smaller than sorted element array[k], and on locations
620 * array[k+1] ... array[length-1] contains unsorted elements greater
621 * than sorted element array[k].
622 *
623 * @param k Position of sorted element to be retrieved.
624 * @param array Array to be used for retrieving k-th sorted element.
625 * Provided array is passed by reference and modified upon execution of
626 * this method so that k-th location contains k-th sorted element, and
627 * array[0] ... array[k-1] contains unsorted elements smaller than
628 * sorted element array[k] and array[k+1] ... array[length-1] contains
629 * elements greater than sorted element array[k].
630 * @param comparator Determines whether an element is greater or lower
631 * than another one.
632 * @return The k-th sorted element in provided array.
633 * @throws IllegalArgumentException k < array.length.
634 */
635 public T select(final int k, final T[] array, final Comparator<T> comparator) {
636 return select(k, array, 0, array.length, comparator);
637 }
638
639 /**
640 * Returns the k-th sorted element in provided array.
641 * Selecting an element is usually faster than sorting the whole
642 * array, and for that reason, when only a few sorted elements are
643 * required, this method should be used instead of sort.
644 * Because array is passed by reference, after executing this method
645 * array is modified so that in k location it contains the k-th sorted
646 * elements and on locations array[0] ... array[k-1] contains unsorted
647 * elements smaller than sorted element array[k], and on locations
648 * array[k+1] ... array[length-1] contains unsorted elements greater
649 * than sorted element array[k].
650 *
651 * @param k Position of sorted element to be retrieved.
652 * @param array Array to be used for retrieving k-th sorted element.
653 * Provided array is passed by reference and modified upon execution of
654 * this method so that k-th location contains k-th sorted element, and
655 * array[0] ... array[k-1] contains unsorted elements smaller than
656 * sorted element array[k] and array[k+1] ... array[length-1] contains
657 * elements greater than sorted element array[k].
658 * @return The k-th sorted element in provided array.
659 * @throws IllegalArgumentException k < array.length.
660 */
661 public double select(final int k, final double[] array) {
662 return select(k, array, 0, array.length);
663 }
664
665 /**
666 * Returns the k-th sorted element in provided array.
667 * Selecting an element is usually faster than sorting the whole
668 * array, and for that reason, when only a few sorted elements are
669 * required, this method should be used instead of sort.
670 * Because array is passed by reference, after executing this method
671 * array is modified so that in k location it contains the k-th sorted
672 * elements and on locations array[0] ... array[k-1] contains unsorted
673 * elements smaller than sorted element array[k], and on locations
674 * array[k+1] ... array[length-1] contains unsorted elements greater
675 * than sorted element array[k].
676 *
677 * @param k Position of sorted element to be retrieved.
678 * @param array Array to be used for retrieving k-th sorted element.
679 * Provided array is passed by reference and modified upon execution of
680 * this method so that k-th location contains k-th sorted element, and
681 * array[0] ... array[k-1] contains unsorted elements smaller than
682 * sorted element array[k] and array[k+1] ... array[length-1] contains
683 * elements greater than sorted element array[k].
684 * @return The k-th sorted element in provided array.
685 * @throws IllegalArgumentException k < array.length.
686 */
687 public float select(final int k, final float[] array) {
688 return select(k, array, 0, array.length);
689 }
690
691 /**
692 * Returns the k-th sorted element in provided array.
693 * Selecting an element is usually faster than sorting the whole
694 * array, and for that reason, when only a few sorted elements are
695 * required, this method should be used instead of sort.
696 * Because array is passed by reference, after executing this method
697 * array is modified so that in k location it contains the k-th sorted
698 * elements and on locations array[0] ... array[k-1] contains unsorted
699 * elements smaller than sorted element array[k], and on locations
700 * array[k+1] ... array[length-1] contains unsorted elements greater
701 * than sorted element array[k].
702 *
703 * @param k Position of sorted element to be retrieved.
704 * @param array Array to be used for retrieving k-th sorted element.
705 * Provided array is passed by reference and modified upon execution of
706 * this method so that k-th location contains k-th sorted element, and
707 * array[0] ... array[k-1] contains unsorted elements smaller than
708 * sorted element array[k] and array[k+1] ... array[length-1] contains
709 * elements greater than sorted element array[k].
710 * @return The k-th sorted element in provided array.
711 * @throws IllegalArgumentException k < array.length.
712 */
713 public int select(final int k, final int[] array) {
714 return select(k, array, 0, array.length);
715 }
716
717 /**
718 * Returns the k-th sorted element in provided array.
719 * Selecting an element is usually faster than sorting the whole
720 * array, and for that reason, when only a few sorted elements are
721 * required, this method should be used instead of sort.
722 * Because array is passed by reference, after executing this method
723 * array is modified so that in k location it contains the k-th sorted
724 * elements and on locations array[0] ... array[k-1] contains unsorted
725 * elements smaller than sorted element array[k], and on locations
726 * array[k+1] ... array[length-1] contains unsorted elements greater
727 * than sorted element array[k].
728 *
729 * @param k Position of sorted element to be retrieved.
730 * @param array Array to be used for retrieving k-th sorted element.
731 * Provided array is passed by reference and modified upon execution of
732 * this method so that k-th location contains k-th sorted element, and
733 * array[0] ... array[k-1] contains unsorted elements smaller than
734 * sorted element array[k] and array[k+1] ... array[length-1] contains
735 * elements greater than sorted element array[k].
736 * @return The k-th sorted element in provided array.
737 * @throws IllegalArgumentException k < array.length.
738 */
739 public long select(final int k, final long[] array) {
740 return select(k, array, 0, array.length);
741 }
742
743 /**
744 * Returns the k-th sorted element in provided array of {@link Comparable}
745 * starting at fromIndex and finishing at toIndex, elements outside this
746 * range are ignored.
747 * Selecting an element is usually faster than sorting the whole
748 * array, and for that reason, when only a few sorted elements are
749 * required, this method should be used instead of sort.
750 * Because array is passed by reference, after executing this method
751 * array is modified so that in k location it contains the k-th sorted
752 * elements and on locations array[fromIndex] ... array[k-1 + fromIndex]
753 * contains unsorted elements smaller than sorted element
754 * array[k + fromIndex], and on locations
755 * array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted
756 * elements greater than sorted element array[k + fromIndex]
757 *
758 * @param k Position of sorted element to be retrieved.
759 * @param array Array to be used for retrieving k-th sorted element.
760 * Provided array is passed by reference and modified upon execution of
761 * this method so that k-th location contains k-th sorted element, and
762 * array[fromIndex] ... array[k-1 + fromIndex] contains unsorted
763 * elements smaller than sorted element array[k + fromIndex] and
764 * array[k+1 + fromIndex] ... array[toIndex-1] contains elements
765 * greater than sorted element array[k].
766 * @param comparator Determines whether an element is greater or lower
767 * than another one.
768 * @param fromIndex Index were sorting starts (inclusive).
769 * @param toIndex Index were sorting stops (exclusive).
770 * @return The k-th sorted element in provided array.
771 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
772 * fromIndex < toIndex.
773 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
774 * outside array boundaries.
775 */
776 public T select(final int k, final T[] array, final int fromIndex, final int toIndex,
777 final Comparator<T> comparator) {
778
779 if (fromIndex > toIndex) {
780 throw new IllegalArgumentException();
781 }
782 if (fromIndex < 0 || toIndex > array.length) {
783 throw new ArrayIndexOutOfBoundsException();
784 }
785
786 int i;
787 int ir;
788 int j;
789 int l;
790 int mid;
791 final var n = toIndex - fromIndex;
792 if (k >= n) {
793 throw new IllegalArgumentException();
794 }
795
796 T a;
797 l = 0;
798 ir = n - 1;
799 for (; ; ) {
800 if (ir <= l + 1) {
801 if (ir == l + 1 && comparator.compare(array[ir + fromIndex], array[l + fromIndex]) < 0) {
802 swap(array, l + fromIndex, ir + fromIndex);
803 }
804 return array[k + fromIndex];
805 } else {
806 mid = (l + ir) >> 1;
807 swap(array, mid + fromIndex, l + 1 + fromIndex);
808 if (comparator.compare(array[l + fromIndex], array[ir + fromIndex]) > 0) {
809 swap(array, l + fromIndex, ir + fromIndex);
810 }
811 if (comparator.compare(array[l + 1 + fromIndex], array[ir + fromIndex]) > 0) {
812 swap(array, l + 1 + fromIndex, ir + fromIndex);
813 }
814 if (comparator.compare(array[l + fromIndex], array[l + 1 + fromIndex]) > 0) {
815 swap(array, l + fromIndex, l + 1 + fromIndex);
816 }
817 i = l + 1;
818 j = ir;
819 a = array[l + 1 + fromIndex];
820 for (; ; ) {
821 do {
822 i++;
823 } while (comparator.compare(array[i + fromIndex], a) < 0);
824
825 do {
826 j--;
827 } while (comparator.compare(array[j + fromIndex], a) > 0);
828
829 if (j < i) {
830 break;
831 }
832
833 swap(array, i + fromIndex, j + fromIndex);
834 }
835 array[l + 1 + fromIndex] = array[j + fromIndex];
836 array[j + fromIndex] = a;
837 if (j >= k) {
838 ir = j - 1;
839 }
840 if (j <= k) {
841 l = i;
842 }
843 }
844 }
845 }
846
847 /**
848 * Returns the k-th sorted element in provided array of {@link Comparable}
849 * starting at fromIndex and finishing at toIndex, elements outside this
850 * range are ignored.
851 * Selecting an element is usually faster than sorting the whole
852 * array, and for that reason, when only a few sorted elements are
853 * required, this method should be used instead of sort.
854 * Because array is passed by reference, after executing this method
855 * array is modified so that in k location it contains the k-th sorted
856 * elements and on locations array[fromIndex] ... array[k-1 + fromIndex]
857 * contains unsorted elements smaller than sorted element
858 * array[k + fromIndex], and on locations
859 * array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted
860 * elements greater than sorted element array[k + fromIndex].
861 *
862 * @param k Position of sorted element to be retrieved.
863 * @param array Array to be used for retrieving k-th sorted element.
864 * Provided array is passed by reference and modified upon execution of
865 * this method so that k-th location contains k-th sorted element, and
866 * array[fromIndex] ... array[k-1 + fromIndex] contains unsorted
867 * elements smaller than sorted element array[k + fromIndex] and
868 * array[k+1 + fromIndex] ... array[toIndex-1] contains elements
869 * greater than sorted element array[k].
870 * @param fromIndex Index were sorting starts (inclusive).
871 * @param toIndex Index were sorting stops (exclusive).
872 * @return The k-th sorted element in provided array.
873 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
874 * fromIndex < toIndex.
875 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
876 * outside array boundaries.
877 */
878 public double select(final int k, final double[] array, final int fromIndex, final int toIndex) {
879
880 if (fromIndex > toIndex) {
881 throw new IllegalArgumentException();
882 }
883 if (fromIndex < 0 || toIndex > array.length) {
884 throw new ArrayIndexOutOfBoundsException();
885 }
886
887 int i;
888 int ir;
889 int j;
890 int l;
891 int mid;
892 final var n = toIndex - fromIndex;
893 if (k >= n) {
894 throw new IllegalArgumentException();
895 }
896
897 double a;
898 l = 0;
899 ir = n - 1;
900 for (; ; ) {
901 if (ir <= l + 1) {
902 if (ir == l + 1 && array[ir + fromIndex] < array[l + fromIndex]) {
903 swap(array, l + fromIndex, ir + fromIndex);
904 }
905 return array[k + fromIndex];
906 } else {
907 mid = (l + ir) >> 1;
908 swap(array, mid + fromIndex, l + 1 + fromIndex);
909 if (array[l + fromIndex] > array[ir + fromIndex]) {
910 swap(array, l + fromIndex, ir + fromIndex);
911 }
912 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
913 swap(array, l + 1 + fromIndex, ir + fromIndex);
914 }
915 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
916 swap(array, l + fromIndex, l + 1 + fromIndex);
917 }
918 i = l + 1;
919 j = ir;
920 a = array[l + 1 + fromIndex];
921 for (; ; ) {
922 do {
923 i++;
924 } while (array[i + fromIndex] < a);
925
926 do {
927 j--;
928 } while (array[j + fromIndex] > a);
929
930 if (j < i) {
931 break;
932 }
933
934 swap(array, i + fromIndex, j + fromIndex);
935 }
936 array[l + 1 + fromIndex] = array[j + fromIndex];
937 array[j + fromIndex] = a;
938 if (j >= k) {
939 ir = j - 1;
940 }
941 if (j <= k) {
942 l = i;
943 }
944 }
945 }
946 }
947
948 /**
949 * Returns the k-th sorted element in provided array of {@link Comparable}
950 * starting at fromIndex and finishing at toIndex, elements outside this
951 * range are ignored.
952 * Selecting an element is usually faster than sorting the whole
953 * array, and for that reason, when only a few sorted elements are
954 * required, this method should be used instead of sort.
955 * Because array is passed by reference, after executing this method
956 * array is modified so that in k location it contains the k-th sorted
957 * elements and on locations array[fromIndex] ... array[k-1 + fromIndex]
958 * contains unsorted elements smaller than sorted element
959 * array[k + fromIndex], and on locations
960 * array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted
961 * elements greater than sorted element array[k + fromIndex].
962 *
963 * @param k Position of sorted element to be retrieved.
964 * @param array Array to be used for retrieving k-th sorted element.
965 * Provided array is passed by reference and modified upon execution of
966 * this method so that k-th location contains k-th sorted element, and
967 * array[fromIndex] ... array[k-1 + fromIndex] contains unsorted
968 * elements smaller than sorted element array[k + fromIndex] and
969 * array[k+1 + fromIndex] ... array[toIndex-1] contains elements
970 * greater than sorted element array[k].
971 * @param fromIndex Index were sorting starts (inclusive).
972 * @param toIndex Index were sorting stops (exclusive).
973 * @return The k-th sorted element in provided array.
974 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
975 * fromIndex < toIndex.
976 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
977 * outside array boundaries.
978 */
979 public float select(final int k, final float[] array, final int fromIndex, final int toIndex) {
980
981 if (fromIndex > toIndex) {
982 throw new IllegalArgumentException();
983 }
984 if (fromIndex < 0 || toIndex > array.length) {
985 throw new ArrayIndexOutOfBoundsException();
986 }
987
988 int i;
989 int ir;
990 int j;
991 int l;
992 int mid;
993 final var n = toIndex - fromIndex;
994 if (k >= n) {
995 throw new IllegalArgumentException();
996 }
997
998 float a;
999 l = 0;
1000 ir = n - 1;
1001 for (; ; ) {
1002 if (ir <= l + 1) {
1003 if (ir == l + 1 && array[ir + fromIndex] < array[l + fromIndex]) {
1004 swap(array, l + fromIndex, ir + fromIndex);
1005 }
1006 return array[k + fromIndex];
1007 } else {
1008 mid = (l + ir) >> 1;
1009 swap(array, mid + fromIndex, l + 1 + fromIndex);
1010 if (array[l + fromIndex] > array[ir + fromIndex]) {
1011 swap(array, l + fromIndex, ir + fromIndex);
1012 }
1013 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
1014 swap(array, l + 1 + fromIndex, ir + fromIndex);
1015 }
1016 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
1017 swap(array, l + fromIndex, l + 1 + fromIndex);
1018 }
1019 i = l + 1;
1020 j = ir;
1021 a = array[l + 1 + fromIndex];
1022 for (; ; ) {
1023 do {
1024 i++;
1025 } while (array[i + fromIndex] < a);
1026
1027 do {
1028 j--;
1029 } while (array[j + fromIndex] > a);
1030
1031 if (j < i) {
1032 break;
1033 }
1034
1035 swap(array, i + fromIndex, j + fromIndex);
1036 }
1037 array[l + 1 + fromIndex] = array[j + fromIndex];
1038 array[j + fromIndex] = a;
1039 if (j >= k) {
1040 ir = j - 1;
1041 }
1042 if (j <= k) {
1043 l = i;
1044 }
1045 }
1046 }
1047 }
1048
1049 /**
1050 * Returns the k-th sorted element in provided array of {@link Comparable}
1051 * starting at fromIndex and finishing at toIndex, elements outside this
1052 * range are ignored.
1053 * Selecting an element is usually faster than sorting the whole
1054 * array, and for that reason, when only a few sorted elements are
1055 * required, this method should be used instead of sort.
1056 * Because array is passed by reference, after executing this method
1057 * array is modified so that in k location it contains the k-th sorted
1058 * elements and on locations array[fromIndex] ... array[k-1 + fromIndex]
1059 * contains unsorted elements smaller than sorted element
1060 * array[k + fromIndex], and on locations
1061 * array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted
1062 * elements greater than sorted element array[k + fromIndex].
1063 *
1064 * @param k Position of sorted element to be retrieved.
1065 * @param array Array to be used for retrieving k-th sorted element.
1066 * Provided array is passed by reference and modified upon execution of
1067 * this method so that k-th location contains k-th sorted element, and
1068 * array[fromIndex] ... array[k-1 + fromIndex] contains unsorted
1069 * elements smaller than sorted element array[k + fromIndex] and
1070 * array[k+1 + fromIndex] ... array[toIndex-1] contains elements
1071 * greater than sorted element array[k].
1072 * @param fromIndex Index were sorting starts (inclusive).
1073 * @param toIndex Index were sorting stops (exclusive).
1074 * @return The k-th sorted element in provided array.
1075 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
1076 * fromIndex < toIndex.
1077 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
1078 * outside array boundaries.
1079 */
1080 public int select(final int k, final int[] array, final int fromIndex, final int toIndex) {
1081
1082 if (fromIndex > toIndex) {
1083 throw new IllegalArgumentException();
1084 }
1085 if (fromIndex < 0 || toIndex > array.length) {
1086 throw new ArrayIndexOutOfBoundsException();
1087 }
1088
1089 int i;
1090 int ir;
1091 int j;
1092 int l;
1093 int mid;
1094 final var n = toIndex - fromIndex;
1095 if (k >= n) {
1096 throw new IllegalArgumentException();
1097 }
1098
1099 int a;
1100 l = 0;
1101 ir = n - 1;
1102 for (; ; ) {
1103 if (ir <= l + 1) {
1104 if (ir == l + 1 && array[ir + fromIndex] < array[l + fromIndex]) {
1105 swap(array, l + fromIndex, ir + fromIndex);
1106 }
1107 return array[k + fromIndex];
1108 } else {
1109 mid = (l + ir) >> 1;
1110 swap(array, mid + fromIndex, l + 1 + fromIndex);
1111 if (array[l + fromIndex] > array[ir + fromIndex]) {
1112 swap(array, l + fromIndex, ir + fromIndex);
1113 }
1114 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
1115 swap(array, l + 1 + fromIndex, ir + fromIndex);
1116 }
1117 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
1118 swap(array, l + fromIndex, l + 1 + fromIndex);
1119 }
1120 i = l + 1;
1121 j = ir;
1122 a = array[l + 1 + fromIndex];
1123 for (; ; ) {
1124 do {
1125 i++;
1126 } while (array[i + fromIndex] < a);
1127
1128 do {
1129 j--;
1130 } while (array[j + fromIndex] > a);
1131
1132 if (j < i) {
1133 break;
1134 }
1135
1136 swap(array, i + fromIndex, j + fromIndex);
1137 }
1138 array[l + 1 + fromIndex] = array[j + fromIndex];
1139 array[j + fromIndex] = a;
1140 if (j >= k) {
1141 ir = j - 1;
1142 }
1143 if (j <= k) {
1144 l = i;
1145 }
1146 }
1147 }
1148 }
1149
1150 /**
1151 * Returns the k-th sorted element in provided array of {@link Comparable}
1152 * starting at fromIndex and finishing at toIndex, elements outside this
1153 * range are ignored.
1154 * Selecting an element is usually faster than sorting the whole
1155 * array, and for that reason, when only a few sorted elements are
1156 * required, this method should be used instead of sort.
1157 * Because array is passed by reference, after executing this method
1158 * array is modified so that in k location it contains the k-th sorted
1159 * elements and on locations array[fromIndex] ... array[k-1 + fromIndex]
1160 * contains unsorted elements smaller than sorted element
1161 * array[k + fromIndex], and on locations
1162 * array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted
1163 * elements greater than sorted element array[k + fromIndex].
1164 *
1165 * @param k Position of sorted element to be retrieved.
1166 * @param array Array to be used for retrieving k-th sorted element.
1167 * Provided array is passed by reference and modified upon execution of
1168 * this method so that k-th location contains k-th sorted element, and
1169 * array[fromIndex] ... array[k-1 + fromIndex] contains unsorted
1170 * elements smaller than sorted element array[k + fromIndex] and
1171 * array[k+1 + fromIndex] ... array[toIndex-1] contains elements
1172 * greater than sorted element array[k].
1173 * @param fromIndex Index were sorting starts (inclusive).
1174 * @param toIndex Index were sorting stops (exclusive).
1175 * @return The k-th sorted element in provided array.
1176 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
1177 * fromIndex < toIndex.
1178 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
1179 * outside array boundaries.
1180 */
1181 public long select(final int k, final long[] array, final int fromIndex, final int toIndex) {
1182
1183 if (fromIndex > toIndex) {
1184 throw new IllegalArgumentException();
1185 }
1186 if (fromIndex < 0 || toIndex > array.length) {
1187 throw new ArrayIndexOutOfBoundsException();
1188 }
1189
1190 int i;
1191 int ir;
1192 int j;
1193 int l;
1194 int mid;
1195 final var n = toIndex - fromIndex;
1196 if (k >= n) {
1197 throw new IllegalArgumentException();
1198 }
1199
1200 long a;
1201 l = 0;
1202 ir = n - 1;
1203 for (; ; ) {
1204 if (ir <= l + 1) {
1205 if (ir == l + 1 && array[ir + fromIndex] < array[l + fromIndex]) {
1206 swap(array, l + fromIndex, ir + fromIndex);
1207 }
1208 return array[k + fromIndex];
1209 } else {
1210 mid = (l + ir) >> 1;
1211 swap(array, mid + fromIndex, l + 1 + fromIndex);
1212 if (array[l + fromIndex] > array[ir + fromIndex]) {
1213 swap(array, l + fromIndex, ir + fromIndex);
1214 }
1215 if (array[l + 1 + fromIndex] > array[ir + fromIndex]) {
1216 swap(array, l + 1 + fromIndex, ir + fromIndex);
1217 }
1218 if (array[l + fromIndex] > array[l + 1 + fromIndex]) {
1219 swap(array, l + fromIndex, l + 1 + fromIndex);
1220 }
1221 i = l + 1;
1222 j = ir;
1223 a = array[l + 1 + fromIndex];
1224 for (; ; ) {
1225 do {
1226 i++;
1227 } while (array[i + fromIndex] < a);
1228
1229 do {
1230 j--;
1231 } while (array[j + fromIndex] > a);
1232
1233 if (j < i) {
1234 break;
1235 }
1236
1237 swap(array, i + fromIndex, j + fromIndex);
1238 }
1239 array[l + 1 + fromIndex] = array[j + fromIndex];
1240 array[j + fromIndex] = a;
1241 if (j >= k) {
1242 ir = j - 1;
1243 }
1244 if (j <= k) {
1245 l = i;
1246 }
1247 }
1248 }
1249 }
1250
1251 /**
1252 * Computes median of provided array
1253 * Median is computed by selecting the length / 2 element, hence
1254 * provided array is modified upon execution of this method containing
1255 * sorted element at location length / 2, smaller unsorted elements at
1256 * array[0] ... array[length / 2 - 1], and greater unsorted elements at
1257 * array[length / 2 + 1] ... array[length - 1].
1258 *
1259 * @param array Array to be used for computation of median. This array
1260 * is modified after execution of this method.
1261 * @return Median of provided array.
1262 */
1263 public T median(final Comparable<T>[] array) {
1264 return median(array, 0, array.length);
1265 }
1266
1267 /**
1268 * Computes median of provided array of {@link Comparable}
1269 * Median is computed by selecting the
1270 * ((toIndex - fromIndex) + fromIndex) / 2 element, hence
1271 * provided array is modified upon execution of this method containing
1272 * sorted element at location ((toIndex - fromIndex) + fromIndex) / 2,
1273 * smaller unsorted elements at array[fromIndex] ...
1274 * array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater
1275 * unsorted elements at
1276 * array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ...
1277 * array[toIndex - 1].
1278 *
1279 * @param array Array to be used for computation of median. This array
1280 * is modified after execution of this method.
1281 * @param fromIndex Index were sorting starts (inclusive).
1282 * @param toIndex Index were sorting stops (exclusive).
1283 * @return Median of provided array.
1284 * @throws IllegalArgumentException if k < (toIndex - fromIndex) or
1285 * fromIndex < toIndex.
1286 * @throws ArrayIndexOutOfBoundsException if fromIndex or toIndex are
1287 * outside array boundaries.
1288 */
1289 @SuppressWarnings("unchecked")
1290 public T median(final Comparable<T>[] array, final int fromIndex, final int toIndex) {
1291
1292 return median((T[]) array, fromIndex, toIndex, new ComparatorAndAverager<>() {
1293 @Override
1294 public int compare(final T t1, final T t2) {
1295 final var t1b = (Comparable<T>) t1;
1296 return t1b.compareTo(t2);
1297 }
1298
1299 @Override
1300 public T average(final T t1, final T t2) {
1301 if (t1 instanceof ComparableAndAverageable && t2 instanceof ComparableAndAverageable) {
1302 return ((ComparableAndAverageable<T>) t1).averageWith(t2);
1303 }
1304 if (t1 instanceof Byte b1 && t2 instanceof Byte b2) {
1305 return (T) Byte.valueOf((byte) ((b1 + b2) / 2));
1306 }
1307 if (t1 instanceof Character c1 && t2 instanceof Character c2) {
1308 return (T) Character.valueOf((char) ((c1 + c2) / 2));
1309 }
1310 if (t1 instanceof Short c1 && t2 instanceof Short c2) {
1311 return (T) Short.valueOf((short) ((c1 + c2) / 2));
1312 }
1313 if (t1 instanceof Integer i1 && t2 instanceof Integer i2) {
1314 return (T) Integer.valueOf((i1 + i2) / 2);
1315 }
1316 if (t1 instanceof Long l1 && t2 instanceof Long l2) {
1317 return (T) Long.valueOf((l1 + l2) / 2);
1318 }
1319 if (t1 instanceof Float f1 && t2 instanceof Float f2) {
1320 return (T) Float.valueOf((f1 + f2) / 2.0f);
1321 }
1322 if (t1 instanceof Double d1 && t2 instanceof Double d2) {
1323 return (T) Double.valueOf((d1 + d2) / 2.0);
1324 }
1325
1326 // for other case, average returns 1st parameter
1327 return t1;
1328 }
1329 });
1330 }
1331
1332 /**
1333 * Computes median of provided array
1334 * Median is computed by selecting the length / 2 element, hence
1335 * provided array is modified upon execution of this method containing
1336 * sorted element at location length / 2, smaller unsorted elements at
1337 * array[0] ... array[length / 2 - 1], and greater unsorted elements at
1338 * array[length / 2 + 1] ... array[length - 1].
1339 *
1340 * @param array Array to be used for computation of median. This array
1341 * is modified after execution of this method.
1342 * @param comparator Determines whether an element is greater or lower
1343 * than another one and also is capable of computing the average
1344 * between two T instances.
1345 * @return Median of provided array.
1346 */
1347 public T median(final T[] array, final ComparatorAndAverager<T> comparator) {
1348 return median(array, 0, array.length, comparator);
1349 }
1350
1351 /**
1352 * Computes median of provided array
1353 * Median is computed by selecting the length / 2 element, hence
1354 * provided array is modified upon execution of this method containing
1355 * sorted element at location length / 2, smaller unsorted elements at
1356 * array[0] ... array[length / 2 - 1], and greater unsorted elements at
1357 * array[length / 2 + 1] ... array[length - 1].
1358 *
1359 * @param array Array to be used for computation of median. This array
1360 * is modified after execution of this method.
1361 * @return Median of provided array.
1362 */
1363 public double median(final double[] array) {
1364 return median(array, 0, array.length);
1365 }
1366
1367 /**
1368 * Computes median of provided array.
1369 * Median is computed by selecting the length / 2 element, hence
1370 * provided array is modified upon execution of this method containing
1371 * sorted element at location length / 2, smaller unsorted elements at
1372 * array[0] ... array[length / 2 - 1], and greater unsorted elements at
1373 * array[length / 2 + 1] ... array[length - 1].
1374 *
1375 * @param array Array to be used for computation of median. This array
1376 * is modified after execution of this method.
1377 * @return Median of provided array.
1378 */
1379 public float median(final float[] array) {
1380 return median(array, 0, array.length);
1381 }
1382
1383 /**
1384 * Computes median of provided array.
1385 * Median is computed by selecting the length / 2 element, hence
1386 * provided array is modified upon execution of this method containing
1387 * sorted element at location length / 2, smaller unsorted elements at
1388 * array[0] ... array[length / 2 - 1], and greater unsorted elements at
1389 * array[length / 2 + 1] ... array[length - 1].
1390 *
1391 * @param array Array to be used for computation of median. This array
1392 * is modified after execution of this method.
1393 * @return Median of provided array.
1394 */
1395 public int median(final int[] array) {
1396 return median(array, 0, array.length);
1397 }
1398
1399 /**
1400 * Computes median of provided array.
1401 * Median is computed by selecting the length / 2 element, hence
1402 * provided array is modified upon execution of this method containing
1403 * sorted element at location length / 2, smaller unsorted elements at
1404 * array[0] ... array[length / 2 - 1], and greater unsorted elements at
1405 * array[length / 2 + 1] ... array[length - 1].
1406 *
1407 * @param array Array to be used for computation of median. This array
1408 * is modified after execution of this method.
1409 * @return Median of provided array.
1410 */
1411 public long median(final long[] array) {
1412 return median(array, 0, array.length);
1413 }
1414
1415
1416 /**
1417 * Computes median of provided array.
1418 * Median is computed by selecting the
1419 * ((toIndex - fromIndex) + fromIndex) / 2 element, hence
1420 * provided array is modified upon execution of this method containing
1421 * sorted element at location ((toIndex - fromIndex) + fromIndex) / 2,
1422 * smaller unsorted elements at array[fromIndex] ...
1423 * array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater
1424 * unsorted elements at
1425 * array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ...
1426 * array[toIndex - 1].
1427 *
1428 * @param array Array to be used for computation of median. This array
1429 * is modified after execution of this method.
1430 * @param fromIndex Index were sorting starts (inclusive).
1431 * @param toIndex Index were sorting stops (exclusive).
1432 * @param comparator Determines whether an element is greater or lower
1433 * than another one and also is capable of computing the average
1434 * between two T instances.
1435 * @return Median of provided array.
1436 * @throws IllegalArgumentException if fromIndex is greater than toIndex.
1437 * @throws ArrayIndexOutOfBoundsException if either fromIndex or toIndex are out of bounds.
1438 */
1439 public T median(final T[] array, final int fromIndex, final int toIndex,
1440 final ComparatorAndAverager<T> comparator) {
1441
1442 if (fromIndex > toIndex) {
1443 throw new IllegalArgumentException();
1444 }
1445 if (fromIndex < 0 || toIndex > array.length) {
1446 throw new ArrayIndexOutOfBoundsException();
1447 }
1448
1449 final var length = toIndex - fromIndex;
1450 final var pos1 = length / 2;
1451
1452 // select pos1 ordered element of v and modifies v so that
1453 // v(0) ... v(pos1 - 1) < value1 < v(pos1 + 1) ... v(length - 1)
1454 // where v(0) ... v(pos1 - 1) are unordered elements lower than value1
1455 // and v(pos1) ... v(length - 1) are unordered elements greater than
1456 // value1
1457 final var value1 = select(pos1, array, fromIndex, toIndex, comparator);
1458 if ((length % 2) == 0) {
1459 // for even length
1460
1461 // value2 is the previously ordered element of v, which is the maximum
1462 // element within v(0) ... v(pos1 - 1)
1463 var value2 = array[fromIndex];
1464 for (int i = 1; i < pos1; i++) {
1465 final var value3 = array[i + fromIndex];
1466 if (comparator.compare(value3, value2) > 0) {
1467 value2 = value3;
1468 }
1469 }
1470
1471 return comparator.average(value1, value2);
1472 } else {
1473 // for odd length
1474 return value1;
1475 }
1476 }
1477
1478 /**
1479 * Computes median of provided array.
1480 * Median is computed by selecting the
1481 * ((toIndex - fromIndex) + fromIndex) / 2 element, hence
1482 * provided array is modified upon execution of this method containing
1483 * sorted element at location ((toIndex - fromIndex) + fromIndex) / 2,
1484 * smaller unsorted elements at array[fromIndex] ...
1485 * array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater
1486 * unsorted elements at
1487 * array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ...
1488 * array[toIndex - 1].
1489 *
1490 * @param array Array to be used for computation of median. This array
1491 * is modified after execution of this method.
1492 * @param fromIndex Index were sorting starts (inclusive).
1493 * @param toIndex Index were sorting stops (exclusive).
1494 * @return Median of provided array.
1495 * @throws IllegalArgumentException if fromIndex is greater than toIndex.
1496 * @throws ArrayIndexOutOfBoundsException if either fromIndex or toIndex are out of bounds.
1497 */
1498 public double median(final double[] array, final int fromIndex, final int toIndex) {
1499
1500 if (fromIndex > toIndex) {
1501 throw new IllegalArgumentException();
1502 }
1503 if (fromIndex < 0 || toIndex > array.length) {
1504 throw new ArrayIndexOutOfBoundsException();
1505 }
1506
1507 final var length = toIndex - fromIndex;
1508 final var pos1 = length / 2;
1509
1510 // select pos1 ordered element of v and modifies v so that
1511 // v(0) ... v(pos1 - 1) < value1 < v(pos1 + 1) ... v(length - 1)
1512 // where v(0) ... v(pos1 - 1) are unordered elements lower than value1
1513 // and v(pos1) ... v(length - 1) are unordered elements greater than
1514 // value1
1515 final var value1 = select(pos1, array, fromIndex, toIndex);
1516 if ((length % 2) == 0) {
1517 // for even length
1518
1519 // value2 is the previously ordered element of v, which is the maximum
1520 // element within v(0) ... v(pos1 - 1)
1521 var value2 = array[fromIndex];
1522 for (int i = 1; i < pos1; i++) {
1523 final var value3 = array[i + fromIndex];
1524 if (value3 > value2) {
1525 value2 = value3;
1526 }
1527 }
1528
1529 return 0.5 * (value1 + value2);
1530 } else {
1531 // for odd length
1532 return value1;
1533 }
1534 }
1535
1536 /**
1537 * Computes median of provided array.
1538 * Median is computed by selecting the
1539 * ((toIndex - fromIndex) + fromIndex) / 2 element, hence
1540 * provided array is modified upon execution of this method containing
1541 * sorted element at location ((toIndex - fromIndex) + fromIndex) / 2,
1542 * smaller unsorted elements at array[fromIndex] ...
1543 * array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater
1544 * unsorted elements at
1545 * array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ...
1546 * array[toIndex - 1].
1547 *
1548 * @param array Array to be used for computation of median. This array
1549 * is modified after execution of this method.
1550 * @param fromIndex Index were sorting starts (inclusive).
1551 * @param toIndex Index were sorting stops (exclusive).
1552 * @return Median of provided array.
1553 * @throws IllegalArgumentException if fromIndex is greater than toIndex.
1554 * @throws ArrayIndexOutOfBoundsException if either fromIndex or toIndex are out of bounds.
1555 */
1556 public float median(final float[] array, final int fromIndex, final int toIndex) {
1557
1558 if (fromIndex > toIndex) {
1559 throw new IllegalArgumentException();
1560 }
1561 if (fromIndex < 0 || toIndex > array.length) {
1562 throw new ArrayIndexOutOfBoundsException();
1563 }
1564
1565 final var length = toIndex - fromIndex;
1566 final var pos1 = length / 2;
1567
1568 // select pos1 ordered element of v and modifies v so that
1569 // v(0) ... v(pos1 - 1) < value1 < v(pos1 + 1) ... v(length - 1)
1570 // where v(0) ... v(pos1 - 1) are unordered elements lower than value1
1571 // and v(pos1) ... v(length - 1) are unordered elements greater than
1572 // value1
1573 final var value1 = select(pos1, array, fromIndex, toIndex);
1574 if ((length % 2) == 0) {
1575 // for even length
1576
1577 // value2 is the previously ordered element of v, which is the maximum
1578 // element within v(0) ... v(pos1 - 1)
1579 var value2 = array[fromIndex];
1580 for (int i = 1; i < pos1; i++) {
1581 final var value3 = array[i + fromIndex];
1582 if (value3 > value2) {
1583 value2 = value3;
1584 }
1585 }
1586
1587 return 0.5f * (value1 + value2);
1588 } else {
1589 // for odd length
1590 return value1;
1591 }
1592 }
1593
1594 /**
1595 * Computes median of provided array.
1596 * Median is computed by selecting the
1597 * ((toIndex - fromIndex) + fromIndex) / 2 element, hence
1598 * provided array is modified upon execution of this method containing
1599 * sorted element at location ((toIndex - fromIndex) + fromIndex) / 2,
1600 * smaller unsorted elements at array[fromIndex] ...
1601 * array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater
1602 * unsorted elements at
1603 * array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ...
1604 * array[toIndex - 1].
1605 *
1606 * @param array Array to be used for computation of median. This array
1607 * is modified after execution of this method.
1608 * @param fromIndex Index were sorting starts (inclusive).
1609 * @param toIndex Index were sorting stops (exclusive).
1610 * @return Median of provided array.
1611 * @throws IllegalArgumentException if fromIndex is greater than toIndex.
1612 * @throws ArrayIndexOutOfBoundsException if either fromIndex or toIndex are out of bounds.
1613 */
1614 public int median(final int[] array, final int fromIndex, final int toIndex) {
1615
1616 if (fromIndex > toIndex) {
1617 throw new IllegalArgumentException();
1618 }
1619 if (fromIndex < 0 || toIndex > array.length) {
1620 throw new ArrayIndexOutOfBoundsException();
1621 }
1622
1623 final var length = toIndex - fromIndex;
1624 final var pos1 = length / 2;
1625
1626 // select pos1 ordered element of v and modifies v so that
1627 // v(0) ... v(pos1 - 1) < value1 < v(pos1 + 1) ... v(length - 1)
1628 // where v(0) ... v(pos1 - 1) are unordered elements lower than value1
1629 // and v(pos1) ... v(length - 1) are unordered elements greater than
1630 // value1
1631 final var value1 = select(pos1, array, fromIndex, toIndex);
1632 if ((length % 2) == 0) {
1633 // for even length
1634
1635 // value2 is the previously ordered element of v, which is the maximum
1636 // element within v(0) ... v(pos1 - 1)
1637 var value2 = array[fromIndex];
1638 for (int i = 1; i < pos1; i++) {
1639 final var value3 = array[i + fromIndex];
1640 if (value3 > value2) {
1641 value2 = value3;
1642 }
1643 }
1644
1645 return (int) (0.5 * ((double) value1 + (double) value2));
1646 } else {
1647 // for odd length
1648 return value1;
1649 }
1650 }
1651
1652 /**
1653 * Computes median of provided array.
1654 * Median is computed by selecting the
1655 * ((toIndex - fromIndex) + fromIndex) / 2 element, hence
1656 * provided array is modified upon execution of this method containing
1657 * sorted element at location ((toIndex - fromIndex) + fromIndex) / 2,
1658 * smaller unsorted elements at array[fromIndex] ...
1659 * array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater
1660 * unsorted elements at
1661 * array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ...
1662 * array[toIndex - 1].
1663 *
1664 * @param array Array to be used for computation of median. This array
1665 * is modified after execution of this method.
1666 * @param fromIndex Index were sorting starts (inclusive).
1667 * @param toIndex Index were sorting stops (exclusive).
1668 * @return Median of provided array.
1669 * @throws IllegalArgumentException if fromIndex is greater than toIndex.
1670 * @throws ArrayIndexOutOfBoundsException if either fromIndex or toIndex are out of bounds.
1671 */
1672 public long median(final long[] array, final int fromIndex, final int toIndex) {
1673
1674 if (fromIndex > toIndex) {
1675 throw new IllegalArgumentException();
1676 }
1677 if (fromIndex < 0 || toIndex > array.length) {
1678 throw new ArrayIndexOutOfBoundsException();
1679 }
1680
1681 final int length = toIndex - fromIndex;
1682 final var pos1 = length / 2;
1683
1684 // select pos1 ordered element of v and modifies v so that
1685 // v(0) ... v(pos1 - 1) < value1 < v(pos1 + 1) ... v(length - 1)
1686 // where v(0) ... v(pos1 - 1) are unordered elements lower than value1
1687 // and v(pos1) ... v(length - 1) are unordered elements greater than
1688 // value1
1689 final var value1 = select(pos1, array, fromIndex, toIndex);
1690 if ((length % 2) == 0) {
1691 // for even length
1692
1693 // value2 is the previously ordered element of v, which is the maximum
1694 // element within v(0) ... v(pos1 - 1)
1695 var value2 = array[fromIndex];
1696 for (int i = 1; i < pos1; i++) {
1697 final var value3 = array[i + fromIndex];
1698 if (value3 > value2) {
1699 value2 = value3;
1700 }
1701 }
1702
1703 return (long) (0.5 * ((double) value1 + (double) value2));
1704 } else {
1705 // for odd length
1706 return value1;
1707 }
1708 }
1709
1710 /**
1711 * Returns sorting method of an implementation of this class.
1712 *
1713 * @return Sorting method.
1714 */
1715 public abstract SortingMethod getMethod();
1716
1717 /**
1718 * Creates a Sorter instance using DEFAULT_SORTING_METHOD.
1719 *
1720 * @return A sorter instance.
1721 */
1722 public static <T> Sorter<T> create() {
1723 return create(DEFAULT_SORTING_METHOD);
1724 }
1725
1726 /**
1727 * Creates a Sorter instance using provided sorting method.
1728 *
1729 * @param method Method to be used for sorting.
1730 * @return A sorter instance.
1731 */
1732 public static <T> Sorter<T> create(final SortingMethod method) {
1733 return switch (method) {
1734 case STRAIGHT_INSERTION_SORTING_METHOD -> new StraightInsertionSorter<>();
1735 case SHELL_SORTING_METHOD -> new ShellSorter<>();
1736 case HEAPSORT_SORTING_METHOD -> new HeapsortSorter<>();
1737 case QUICKSORT_SORTING_METHOD -> new QuicksortSorter<>();
1738 default -> new SystemSorter<>();
1739 };
1740 }
1741
1742 /**
1743 * Returns a new array containing original indices ordered from 0
1744 * to length-1.
1745 *
1746 * @param length length of returned array.
1747 * @return Array with indices in natural order.
1748 */
1749 protected int[] getInitialIndicesVector(final int length) {
1750 final var out = new int[length];
1751
1752 for (int i = 0; i < length; i++) {
1753 out[i] = i;
1754 }
1755
1756 return out;
1757 }
1758
1759 /**
1760 * Swaps values in array at locations posA and posB.
1761 *
1762 * @param arr array where values are swapped.
1763 * @param posA Location to be swapped.
1764 * @param posB Location to be swapped.
1765 */
1766 protected void swap(final T[] arr, final int posA, final int posB) {
1767 final var value = arr[posA];
1768 arr[posA] = arr[posB];
1769 arr[posB] = value;
1770 }
1771
1772 /**
1773 * Swaps values in array at locations posA and posB.
1774 *
1775 * @param arr array where values are swapped.
1776 * @param posA Location to be swapped.
1777 * @param posB Location to be swapped.
1778 */
1779 protected void swap(final double[] arr, final int posA, final int posB) {
1780 final var value = arr[posA];
1781 arr[posA] = arr[posB];
1782 arr[posB] = value;
1783 }
1784
1785 /**
1786 * Swaps values in array at locations posA and posB.
1787 *
1788 * @param arr array where values are swapped.
1789 * @param posA Location to be swapped.
1790 * @param posB Location to be swapped.
1791 */
1792 protected void swap(final float[] arr, final int posA, final int posB) {
1793 final var value = arr[posA];
1794 arr[posA] = arr[posB];
1795 arr[posB] = value;
1796 }
1797
1798 /**
1799 * Swaps values in array at locations posA and posB.
1800 *
1801 * @param arr array where values are swapped.
1802 * @param posA Location to be swapped.
1803 * @param posB Location to be swapped.
1804 */
1805 protected void swap(final int[] arr, final int posA, final int posB) {
1806 final var value = arr[posA];
1807 arr[posA] = arr[posB];
1808 arr[posB] = value;
1809 }
1810
1811 /**
1812 * Swaps values in array at locations posA and posB.
1813 *
1814 * @param arr array where values are swapped.
1815 * @param posA Location to be swapped.
1816 * @param posB Location to be swapped.
1817 */
1818 protected void swap(final long[] arr, final int posA, final int posB) {
1819 final var value = arr[posA];
1820 arr[posA] = arr[posB];
1821 arr[posB] = value;
1822 }
1823 }