Class |
Line # |
Actions |
|||
---|---|---|---|---|---|
QuickSort | 33 | 219 | 56 | ||
QuickSort.FloatComparator | 39 | 3 | 3 | ||
QuickSort.DoubleComparator | 64 | 5 | 3 | ||
QuickSort.IntComparator | 94 | 3 | 3 | ||
QuickSort.ExternalComparator | 121 | 3 | 3 |
1 | /* | |
2 | * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) | |
3 | * Copyright (C) $$Year-Rel$$ The Jalview Authors | |
4 | * | |
5 | * This file is part of Jalview. | |
6 | * | |
7 | * Jalview is free software: you can redistribute it and/or | |
8 | * modify it under the terms of the GNU General Public License | |
9 | * as published by the Free Software Foundation, either version 3 | |
10 | * of the License, or (at your option) any later version. | |
11 | * | |
12 | * Jalview is distributed in the hope that it will be useful, but | |
13 | * WITHOUT ANY WARRANTY; without even the implied warranty | |
14 | * of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
15 | * PURPOSE. See the GNU General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public License | |
18 | * along with Jalview. If not, see <http://www.gnu.org/licenses/>. | |
19 | * The Jalview Authors are detailed in the 'AUTHORS' file. | |
20 | */ | |
21 | package jalview.util; | |
22 | ||
23 | import java.util.Arrays; | |
24 | import java.util.Comparator; | |
25 | ||
26 | /** | |
27 | * A class to perform efficient sorting of arrays of objects based on arrays of | |
28 | * scores or other attributes. For example, residues by percentage frequency. | |
29 | * | |
30 | * @author gmcarstairs | |
31 | * | |
32 | */ | |
33 | public class QuickSort | |
34 | { | |
35 | /** | |
36 | * A comparator that compares two integers by comparing their respective | |
37 | * indexed values in an array of floats | |
38 | */ | |
39 | static class FloatComparator implements Comparator<Integer> | |
40 | { | |
41 | private final float[] values; | |
42 | ||
43 | private boolean ascending; | |
44 | ||
45 | 3 | FloatComparator(float[] v, boolean asc) |
46 | { | |
47 | 3 | values = v; |
48 | 3 | ascending = asc; |
49 | } | |
50 | ||
51 | 212 | @Override |
52 | public int compare(Integer o1, Integer o2) | |
53 | { | |
54 | 212 | return ascending |
55 | ? Float.compare(values[o1.intValue()], values[o2.intValue()]) | |
56 | : Float.compare(values[o2.intValue()], values[o1.intValue()]); | |
57 | } | |
58 | } | |
59 | ||
60 | /** | |
61 | * A comparator that compares two integers by comparing their respective | |
62 | * indexed values in an array of doubles | |
63 | */ | |
64 | static class DoubleComparator implements Comparator<Integer> | |
65 | { | |
66 | private final double[] values; | |
67 | ||
68 | private boolean ascending; | |
69 | ||
70 | 5 | DoubleComparator(double[] v, boolean asc) |
71 | { | |
72 | 5 | values = v; |
73 | 5 | ascending = asc; |
74 | } | |
75 | ||
76 | 26 | @Override |
77 | public int compare(Integer o1, Integer o2) | |
78 | { | |
79 | 26 | if (ascending) |
80 | { | |
81 | 21 | return Double.compare(values[o1.intValue()], values[o2.intValue()]); |
82 | } | |
83 | else | |
84 | { | |
85 | 5 | return Double.compare(values[o2.intValue()], values[o1.intValue()]); |
86 | } | |
87 | } | |
88 | } | |
89 | ||
90 | /** | |
91 | * A comparator that compares two integers by comparing their respective | |
92 | * indexed values in an array of ints | |
93 | */ | |
94 | static class IntComparator implements Comparator<Integer> | |
95 | { | |
96 | private final int[] values; | |
97 | ||
98 | private boolean ascending; | |
99 | ||
100 | 169855 | IntComparator(int[] v, boolean asc) |
101 | { | |
102 | 169855 | values = v; |
103 | 169856 | ascending = asc; |
104 | } | |
105 | ||
106 | 257327 | @Override |
107 | public int compare(Integer o1, Integer o2) | |
108 | { | |
109 | 257328 | return ascending |
110 | ? Integer.compare(values[o1.intValue()], | |
111 | values[o2.intValue()]) | |
112 | : Integer.compare(values[o2.intValue()], | |
113 | values[o1.intValue()]); | |
114 | } | |
115 | } | |
116 | ||
117 | /** | |
118 | * A comparator that compares two integers by comparing their respective | |
119 | * indexed values in an array of comparable objects. | |
120 | */ | |
121 | static class ExternalComparator implements Comparator<Integer> | |
122 | { | |
123 | private final Comparable[] values; | |
124 | ||
125 | private boolean ascending; | |
126 | ||
127 | 2 | ExternalComparator(Comparable[] v, boolean asc) |
128 | { | |
129 | 2 | values = v; |
130 | 2 | ascending = asc; |
131 | } | |
132 | ||
133 | 16 | @Override |
134 | public int compare(Integer o1, Integer o2) | |
135 | { | |
136 | 16 | return ascending |
137 | ? values[o1.intValue()].compareTo(values[o2.intValue()]) | |
138 | : values[o2.intValue()].compareTo(values[o1.intValue()]); | |
139 | } | |
140 | } | |
141 | ||
142 | /** | |
143 | * Sorts both arrays with respect to ascending order of the items in the first | |
144 | * array. | |
145 | * | |
146 | * @param arr | |
147 | * @param s | |
148 | */ | |
149 | 97 | public static void sort(int[] arr, Object[] s) |
150 | { | |
151 | 97 | sort(arr, 0, arr.length - 1, s); |
152 | } | |
153 | ||
154 | /** | |
155 | * Sorts both arrays with respect to ascending order of the items in the first | |
156 | * array. | |
157 | * | |
158 | * @param arr | |
159 | * @param s | |
160 | */ | |
161 | 1 | public static void sort(float[] arr, Object[] s) |
162 | { | |
163 | 1 | sort(arr, 0, arr.length - 1, s); |
164 | } | |
165 | ||
166 | /** | |
167 | * Sorts both arrays with respect to ascending order of the items in the first | |
168 | * array. | |
169 | * | |
170 | * @param arr | |
171 | * @param s | |
172 | */ | |
173 | 1 | public static void sort(double[] arr, Object[] s) |
174 | { | |
175 | 1 | sort(arr, 0, arr.length - 1, s); |
176 | } | |
177 | ||
178 | /** | |
179 | * Sorts both arrays with respect to descending order of the items in the | |
180 | * first array. The sorting is case-sensitive. | |
181 | * | |
182 | * @param arr | |
183 | * @param s | |
184 | */ | |
185 | 1724 | public static void sort(String[] arr, Object[] s) |
186 | { | |
187 | 1724 | stringSort(arr, 0, arr.length - 1, s); |
188 | } | |
189 | ||
190 | 7506 | static void stringSort(String[] arr, int p, int r, Object[] s) |
191 | { | |
192 | 7506 | int q; |
193 | ||
194 | 7506 | if (p < r) |
195 | { | |
196 | 2891 | q = stringPartition(arr, p, r, s); |
197 | 2891 | stringSort(arr, p, q, s); |
198 | 2891 | stringSort(arr, q + 1, r, s); |
199 | } | |
200 | } | |
201 | ||
202 | 9 | static void sort(float[] arr, int p, int r, Object[] s) |
203 | { | |
204 | 9 | int q; |
205 | ||
206 | 9 | if (p < r) |
207 | { | |
208 | 4 | q = partition(arr, p, r, s); |
209 | 4 | sort(arr, p, q, s); |
210 | 4 | sort(arr, q + 1, r, s); |
211 | } | |
212 | } | |
213 | ||
214 | 9 | static void sort(double[] arr, int p, int r, Object[] s) |
215 | { | |
216 | 9 | int q; |
217 | ||
218 | 9 | if (p < r) |
219 | { | |
220 | 4 | q = partition(arr, p, r, s); |
221 | 4 | sort(arr, p, q, s); |
222 | 4 | sort(arr, q + 1, r, s); |
223 | } | |
224 | } | |
225 | ||
226 | 685 | static void sort(int[] arr, int p, int r, Object[] s) |
227 | { | |
228 | 685 | int q; |
229 | ||
230 | 685 | if (p < r) |
231 | { | |
232 | 294 | q = partition(arr, p, r, s); |
233 | 294 | sort(arr, p, q, s); |
234 | 294 | sort(arr, q + 1, r, s); |
235 | } | |
236 | } | |
237 | ||
238 | 4 | static int partition(float[] arr, int p, int r, Object[] s) |
239 | { | |
240 | 4 | float x = arr[p]; |
241 | 4 | int i = p - 1; |
242 | 4 | int j = r + 1; |
243 | ||
244 | 4 | while (true) |
245 | { | |
246 | 7 | do |
247 | { | |
248 | 10 | j = j - 1; |
249 | 10 | } while (arr[j] > x); |
250 | ||
251 | 7 | do |
252 | { | |
253 | 8 | i = i + 1; |
254 | 8 | } while (arr[i] < x); |
255 | ||
256 | 7 | if (i < j) |
257 | { | |
258 | 3 | float tmp = arr[i]; |
259 | 3 | arr[i] = arr[j]; |
260 | 3 | arr[j] = tmp; |
261 | ||
262 | 3 | Object tmp2 = s[i]; |
263 | 3 | s[i] = s[j]; |
264 | 3 | s[j] = tmp2; |
265 | } | |
266 | else | |
267 | { | |
268 | 4 | return j; |
269 | } | |
270 | } | |
271 | } | |
272 | ||
273 | 0 | static int partition(float[] arr, int p, int r, char[] s) |
274 | { | |
275 | 0 | float x = arr[p]; |
276 | 0 | int i = p - 1; |
277 | 0 | int j = r + 1; |
278 | ||
279 | 0 | while (true) |
280 | { | |
281 | 0 | do |
282 | { | |
283 | 0 | j = j - 1; |
284 | 0 | } while (arr[j] > x); |
285 | ||
286 | 0 | do |
287 | { | |
288 | 0 | i = i + 1; |
289 | 0 | } while (arr[i] < x); |
290 | ||
291 | 0 | if (i < j) |
292 | { | |
293 | 0 | float tmp = arr[i]; |
294 | 0 | arr[i] = arr[j]; |
295 | 0 | arr[j] = tmp; |
296 | ||
297 | 0 | char tmp2 = s[i]; |
298 | 0 | s[i] = s[j]; |
299 | 0 | s[j] = tmp2; |
300 | } | |
301 | else | |
302 | { | |
303 | 0 | return j; |
304 | } | |
305 | } | |
306 | } | |
307 | ||
308 | 294 | static int partition(int[] arr, int p, int r, Object[] s) |
309 | { | |
310 | 294 | int x = arr[p]; |
311 | 294 | int i = p - 1; |
312 | 294 | int j = r + 1; |
313 | ||
314 | 294 | while (true) |
315 | { | |
316 | 429 | do |
317 | { | |
318 | 1064 | j = j - 1; |
319 | 1064 | } while (arr[j] > x); |
320 | ||
321 | 429 | do |
322 | { | |
323 | 488 | i = i + 1; |
324 | 488 | } while (arr[i] < x); |
325 | ||
326 | 429 | if (i < j) |
327 | { | |
328 | 135 | int tmp = arr[i]; |
329 | 135 | arr[i] = arr[j]; |
330 | 135 | arr[j] = tmp; |
331 | ||
332 | 135 | Object tmp2 = s[i]; |
333 | 135 | s[i] = s[j]; |
334 | 135 | s[j] = tmp2; |
335 | } | |
336 | else | |
337 | { | |
338 | 294 | return j; |
339 | } | |
340 | } | |
341 | } | |
342 | ||
343 | 4 | static int partition(double[] arr, int p, int r, Object[] s) |
344 | { | |
345 | 4 | double x = arr[p]; |
346 | 4 | int i = p - 1; |
347 | 4 | int j = r + 1; |
348 | ||
349 | 4 | while (true) |
350 | { | |
351 | 7 | do |
352 | { | |
353 | 10 | j = j - 1; |
354 | 10 | } while (arr[j] > x); |
355 | ||
356 | 7 | do |
357 | { | |
358 | 8 | i = i + 1; |
359 | 8 | } while (arr[i] < x); |
360 | ||
361 | 7 | if (i < j) |
362 | { | |
363 | 3 | double tmp = arr[i]; |
364 | 3 | arr[i] = arr[j]; |
365 | 3 | arr[j] = tmp; |
366 | ||
367 | 3 | Object tmp2 = s[i]; |
368 | 3 | s[i] = s[j]; |
369 | 3 | s[j] = tmp2; |
370 | } | |
371 | else | |
372 | { | |
373 | 4 | return j; |
374 | } | |
375 | } | |
376 | } | |
377 | ||
378 | 2891 | static int stringPartition(String[] arr, int p, int r, Object[] s) |
379 | { | |
380 | 2891 | String x = arr[p]; |
381 | 2891 | int i = p - 1; |
382 | 2891 | int j = r + 1; |
383 | ||
384 | 2891 | while (true) |
385 | { | |
386 | 4578 | do |
387 | { | |
388 | 8379 | j = j - 1; |
389 | 8379 | } while (arr[j].compareTo(x) < 0); |
390 | ||
391 | 4578 | do |
392 | { | |
393 | 5297 | i = i + 1; |
394 | 5297 | } while (arr[i].compareTo(x) > 0); |
395 | ||
396 | 4578 | if (i < j) |
397 | { | |
398 | 1687 | String tmp = arr[i]; |
399 | 1687 | arr[i] = arr[j]; |
400 | 1687 | arr[j] = tmp; |
401 | ||
402 | 1687 | Object tmp2 = s[i]; |
403 | 1687 | s[i] = s[j]; |
404 | 1687 | s[j] = tmp2; |
405 | } | |
406 | else | |
407 | { | |
408 | 2891 | return j; |
409 | } | |
410 | } | |
411 | } | |
412 | ||
413 | /** | |
414 | * Sorts both arrays to give ascending order by the first array, by first | |
415 | * partitioning into zero and non-zero values before sorting the latter. This | |
416 | * is faster than a direct call to charSortByFloat in the case where most of | |
417 | * the array to be sorted is zero. | |
418 | * | |
419 | * @param arr | |
420 | * @param s | |
421 | */ | |
422 | 1 | public static void sort(float[] arr, char[] s) |
423 | { | |
424 | /* | |
425 | * Move all zero values to the front, non-zero to the back, while counting | |
426 | * negative values | |
427 | */ | |
428 | 1 | float[] f1 = new float[arr.length]; |
429 | 1 | char[] s1 = new char[s.length]; |
430 | 1 | int negativeCount = 0; |
431 | 1 | int zerosCount = 0; |
432 | 1 | int nextNonZeroValue = arr.length - 1; |
433 | 65 | for (int i = 0; i < arr.length; i++) |
434 | { | |
435 | 64 | float val = arr[i]; |
436 | 64 | if (val != 0f) |
437 | { | |
438 | 3 | f1[nextNonZeroValue] = val; |
439 | 3 | s1[nextNonZeroValue] = s[i]; |
440 | 3 | nextNonZeroValue--; |
441 | 3 | if (val < 0f) |
442 | { | |
443 | 1 | negativeCount++; |
444 | } | |
445 | } | |
446 | else | |
447 | { | |
448 | 61 | f1[zerosCount] = val; |
449 | 61 | s1[zerosCount] = s[i]; |
450 | 61 | zerosCount++; |
451 | } | |
452 | } | |
453 | 1 | int positiveCount = arr.length - zerosCount - negativeCount; |
454 | ||
455 | 1 | if (zerosCount == arr.length) |
456 | { | |
457 | 0 | return; // all zero |
458 | } | |
459 | ||
460 | /* | |
461 | * sort the non-zero values | |
462 | */ | |
463 | 1 | float[] nonZeroFloats = Arrays.copyOfRange(f1, zerosCount, f1.length); |
464 | 1 | char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length); |
465 | 1 | charSortByFloat(nonZeroFloats, nonZeroChars, true); |
466 | ||
467 | /* | |
468 | * Backfill zero values to original arrays, after the space reserved for | |
469 | * negatives | |
470 | */ | |
471 | 1 | System.arraycopy(f1, 0, arr, negativeCount, zerosCount); |
472 | 1 | System.arraycopy(s1, 0, s, negativeCount, zerosCount); |
473 | ||
474 | /* | |
475 | * Copy sorted negative values to the front of arr, s | |
476 | */ | |
477 | 1 | System.arraycopy(nonZeroFloats, 0, arr, 0, negativeCount); |
478 | 1 | System.arraycopy(nonZeroChars, 0, s, 0, negativeCount); |
479 | ||
480 | /* | |
481 | * Copy sorted positive values after the negatives and zeros | |
482 | */ | |
483 | 1 | System.arraycopy(nonZeroFloats, negativeCount, arr, |
484 | negativeCount + zerosCount, positiveCount); | |
485 | 1 | System.arraycopy(nonZeroChars, negativeCount, s, |
486 | negativeCount + zerosCount, positiveCount); | |
487 | } | |
488 | ||
489 | /** | |
490 | * Sorts arrays of float and char by the float values, by making an array of | |
491 | * indices, and sorting it using a comparator that refers to the float values. | |
492 | * | |
493 | * @see http | |
494 | * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- | |
495 | * after-sorting | |
496 | * @param arr | |
497 | * @param s | |
498 | * @param ascending | |
499 | */ | |
500 | 3 | public static void charSortByFloat(float[] arr, char[] s, |
501 | boolean ascending) | |
502 | { | |
503 | 3 | final int length = arr.length; |
504 | 3 | Integer[] indices = makeIndexArray(length); |
505 | 3 | Arrays.sort(indices, new FloatComparator(arr, ascending)); |
506 | ||
507 | /* | |
508 | * Copy the array values as per the sorted indices | |
509 | */ | |
510 | 3 | float[] sortedFloats = new float[length]; |
511 | 3 | char[] sortedChars = new char[s.length]; |
512 | 134 | for (int i = 0; i < length; i++) |
513 | { | |
514 | 131 | sortedFloats[i] = arr[indices[i]]; |
515 | 131 | sortedChars[i] = s[indices[i]]; |
516 | } | |
517 | ||
518 | /* | |
519 | * And copy the sorted values back into the arrays | |
520 | */ | |
521 | 3 | System.arraycopy(sortedFloats, 0, arr, 0, length); |
522 | 3 | System.arraycopy(sortedChars, 0, s, 0, s.length); |
523 | } | |
524 | ||
525 | /** | |
526 | * Make an array whose values are 0...length. | |
527 | * | |
528 | * @param length | |
529 | * @return | |
530 | */ | |
531 | 169866 | protected static Integer[] makeIndexArray(final int length) |
532 | { | |
533 | 169867 | Integer[] indices = new Integer[length]; |
534 | 495389 | for (int i = 0; i < length; i++) |
535 | { | |
536 | 325521 | indices[i] = i; |
537 | } | |
538 | 169867 | return indices; |
539 | } | |
540 | ||
541 | 0 | static void sort(float[] arr, int p, int r, char[] s) |
542 | { | |
543 | 0 | int q; |
544 | 0 | if (p < r) |
545 | { | |
546 | 0 | q = partition(arr, p, r, s); |
547 | 0 | sort(arr, p, q, s); |
548 | 0 | sort(arr, q + 1, r, s); |
549 | } | |
550 | } | |
551 | ||
552 | /** | |
553 | * Sorts both arrays to give ascending order in the first array, by first | |
554 | * partitioning into zero and non-zero values before sorting the latter. This | |
555 | * is faster than a direct call to charSortByInt in the case where most of the | |
556 | * array to be sorted is zero. | |
557 | * | |
558 | * @param arr | |
559 | * @param s | |
560 | */ | |
561 | 215039 | public static void sort(int[] arr, char[] s) |
562 | { /* | |
563 | * Move all zero values to the front, non-zero to the back, while counting | |
564 | * negative values | |
565 | */ | |
566 | 215039 | int[] f1 = new int[arr.length]; |
567 | 215053 | char[] s1 = new char[s.length]; |
568 | 215054 | int negativeCount = 0; |
569 | 215048 | int zerosCount = 0; |
570 | 215055 | int nextNonZeroValue = arr.length - 1; |
571 | 602072 | for (int i = 0; i < arr.length; i++) |
572 | { | |
573 | 387039 | int val = arr[i]; |
574 | 387043 | if (val != 0f) |
575 | { | |
576 | 325220 | f1[nextNonZeroValue] = val; |
577 | 325225 | s1[nextNonZeroValue] = s[i]; |
578 | 325221 | nextNonZeroValue--; |
579 | 325222 | if (val < 0) |
580 | { | |
581 | 1 | negativeCount++; |
582 | } | |
583 | } | |
584 | else | |
585 | { | |
586 | 61820 | f1[zerosCount] = val; |
587 | 61820 | s1[zerosCount] = s[i]; |
588 | 61820 | zerosCount++; |
589 | } | |
590 | } | |
591 | 215035 | int positiveCount = arr.length - zerosCount - negativeCount; |
592 | ||
593 | 215059 | if (zerosCount == arr.length) |
594 | { | |
595 | 45204 | return; // all zero |
596 | } | |
597 | ||
598 | /* | |
599 | * sort the non-zero values | |
600 | */ | |
601 | 169855 | int[] nonZeroInts = Arrays.copyOfRange(f1, zerosCount, f1.length); |
602 | 169853 | char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length); |
603 | 169854 | charSortByInt(nonZeroInts, nonZeroChars, true); |
604 | ||
605 | /* | |
606 | * Backfill zero values to original arrays, after the space reserved for | |
607 | * negatives | |
608 | */ | |
609 | 169851 | System.arraycopy(f1, 0, arr, negativeCount, zerosCount); |
610 | 169848 | System.arraycopy(s1, 0, s, negativeCount, zerosCount); |
611 | ||
612 | /* | |
613 | * Copy sorted negative values to the front of arr, s | |
614 | */ | |
615 | 169851 | System.arraycopy(nonZeroInts, 0, arr, 0, negativeCount); |
616 | 169851 | System.arraycopy(nonZeroChars, 0, s, 0, negativeCount); |
617 | ||
618 | /* | |
619 | * Copy sorted positive values after the negatives and zeros | |
620 | */ | |
621 | 169857 | System.arraycopy(nonZeroInts, negativeCount, arr, |
622 | negativeCount + zerosCount, positiveCount); | |
623 | 169851 | System.arraycopy(nonZeroChars, negativeCount, s, |
624 | negativeCount + zerosCount, positiveCount); | |
625 | } | |
626 | ||
627 | /** | |
628 | * Sorts arrays of int and char, by making an array of indices, and sorting it | |
629 | * using a comparator that refers to the int values. | |
630 | * | |
631 | * @see http | |
632 | * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- | |
633 | * after-sorting | |
634 | * @param arr | |
635 | * @param s | |
636 | * @param ascending | |
637 | */ | |
638 | 169855 | public static void charSortByInt(int[] arr, char[] s, boolean ascending) |
639 | { | |
640 | 169855 | final int length = arr.length; |
641 | 169856 | Integer[] indices = makeIndexArray(length); |
642 | 169852 | Arrays.sort(indices, new IntComparator(arr, ascending)); |
643 | ||
644 | /* | |
645 | * Copy the array values as per the sorted indices | |
646 | */ | |
647 | 169846 | int[] sortedInts = new int[length]; |
648 | 169855 | char[] sortedChars = new char[s.length]; |
649 | 495201 | for (int i = 0; i < length; i++) |
650 | { | |
651 | 325344 | sortedInts[i] = arr[indices[i]]; |
652 | 325340 | sortedChars[i] = s[indices[i]]; |
653 | } | |
654 | ||
655 | /* | |
656 | * And copy the sorted values back into the arrays | |
657 | */ | |
658 | 169853 | System.arraycopy(sortedInts, 0, arr, 0, length); |
659 | 169855 | System.arraycopy(sortedChars, 0, s, 0, s.length); |
660 | } | |
661 | ||
662 | /** | |
663 | * Sorts arrays of int and Object, by making an array of indices, and sorting | |
664 | * it using a comparator that refers to the int values. | |
665 | * | |
666 | * @see http | |
667 | * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- | |
668 | * after-sorting | |
669 | * @param arr | |
670 | * @param s | |
671 | * @param ascending | |
672 | */ | |
673 | 2 | public static void sortByInt(int[] arr, Object[] s, boolean ascending) |
674 | { | |
675 | 2 | final int length = arr.length; |
676 | 2 | Integer[] indices = makeIndexArray(length); |
677 | 2 | Arrays.sort(indices, new IntComparator(arr, ascending)); |
678 | ||
679 | /* | |
680 | * Copy the array values as per the sorted indices | |
681 | */ | |
682 | 2 | int[] sortedInts = new int[length]; |
683 | 2 | Object[] sortedObjects = new Object[s.length]; |
684 | 12 | for (int i = 0; i < length; i++) |
685 | { | |
686 | 10 | sortedInts[i] = arr[indices[i]]; |
687 | 10 | sortedObjects[i] = s[indices[i]]; |
688 | } | |
689 | ||
690 | /* | |
691 | * And copy the sorted values back into the arrays | |
692 | */ | |
693 | 2 | System.arraycopy(sortedInts, 0, arr, 0, length); |
694 | 2 | System.arraycopy(sortedObjects, 0, s, 0, s.length); |
695 | } | |
696 | ||
697 | /** | |
698 | * Sorts arrays of String and Object, by making an array of indices, and | |
699 | * sorting it using a comparator that refers to the String values. Both arrays | |
700 | * are sorted by case-sensitive order of the string array values. | |
701 | * | |
702 | * @see http | |
703 | * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- | |
704 | * after-sorting | |
705 | * @param arr | |
706 | * @param s | |
707 | * @param ascending | |
708 | */ | |
709 | 2 | public static void sortByString(String[] arr, Object[] s, |
710 | boolean ascending) | |
711 | { | |
712 | 2 | final int length = arr.length; |
713 | 2 | Integer[] indices = makeIndexArray(length); |
714 | 2 | Arrays.sort(indices, new ExternalComparator(arr, ascending)); |
715 | ||
716 | /* | |
717 | * Copy the array values as per the sorted indices | |
718 | */ | |
719 | 2 | String[] sortedStrings = new String[length]; |
720 | 2 | Object[] sortedObjects = new Object[s.length]; |
721 | 12 | for (int i = 0; i < length; i++) |
722 | { | |
723 | 10 | sortedStrings[i] = arr[indices[i]]; |
724 | 10 | sortedObjects[i] = s[indices[i]]; |
725 | } | |
726 | ||
727 | /* | |
728 | * And copy the sorted values back into the arrays | |
729 | */ | |
730 | 2 | System.arraycopy(sortedStrings, 0, arr, 0, length); |
731 | 2 | System.arraycopy(sortedObjects, 0, s, 0, s.length); |
732 | } | |
733 | ||
734 | /** | |
735 | * Sorts arrays of double and Object, by making an array of indices, and | |
736 | * sorting it using a comparator that refers to the double values. | |
737 | * | |
738 | * @see http | |
739 | * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- | |
740 | * after-sorting | |
741 | * @param arr | |
742 | * @param s | |
743 | * @param ascending | |
744 | */ | |
745 | 5 | public static void sortByDouble(double[] arr, Object[] s, |
746 | boolean ascending) | |
747 | { | |
748 | 5 | final int length = arr.length; |
749 | 5 | Integer[] indices = makeIndexArray(length); |
750 | 5 | Arrays.sort(indices, new DoubleComparator(arr, ascending)); |
751 | ||
752 | /* | |
753 | * Copy the array values as per the sorted indices | |
754 | */ | |
755 | 5 | double[] sortedDoubles = new double[length]; |
756 | 5 | Object[] sortedObjects = new Object[s.length]; |
757 | 25 | for (int i = 0; i < length; i++) |
758 | { | |
759 | 20 | sortedDoubles[i] = arr[indices[i]]; |
760 | 20 | sortedObjects[i] = s[indices[i]]; |
761 | } | |
762 | ||
763 | /* | |
764 | * And copy the sorted values back into the arrays | |
765 | */ | |
766 | 5 | System.arraycopy(sortedDoubles, 0, arr, 0, length); |
767 | 5 | System.arraycopy(sortedObjects, 0, s, 0, s.length); |
768 | } | |
769 | } |