2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
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.
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.
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.
23 import java.util.Arrays;
24 import java.util.Comparator;
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.
33 public class QuickSort
35 static class FloatComparator implements Comparator<Integer>
38 private final float[] values;
40 FloatComparator(float[] v)
46 public int compare(Integer o1, Integer o2)
48 return Float.compare(values[o1.intValue()], values[o2]);
53 static class IntComparator implements Comparator<Integer>
56 private final int[] values;
58 IntComparator(int[] v)
64 public int compare(Integer o1, Integer o2)
66 return Integer.compare(values[o1], values[o2]);
72 * Sorts both arrays with respect to ascending order of the items in the first
78 public static void sortInt(int[] arr, Object[] s)
80 sortInt(arr, 0, arr.length - 1, s);
84 * Sorts both arrays with respect to ascending order of the items in the first
90 public static void sortFloatObject(float[] arr, Object[] s)
92 sortFloat(arr, 0, arr.length - 1, s);
96 * Sorts both arrays with respect to ascending order of the items in the first
102 public static void sortDouble(double[] arr, Object[] s)
104 sortDouble(arr, 0, arr.length - 1, s);
108 * Sorts both arrays with respect to descending order of the items in the
114 public static void sort(String[] arr, Object[] s)
116 stringSort(arr, 0, arr.length - 1, s);
119 private static void stringSort(String[] arr, int p, int r, Object[] s)
125 q = stringPartition(arr, p, r, s);
126 stringSort(arr, p, q, s);
127 stringSort(arr, q + 1, r, s);
131 private static void sortFloat(float[] arr, int p, int r, Object[] s)
137 q = partitionFloat(arr, p, r, s);
138 sortFloat(arr, p, q, s);
139 sortFloat(arr, q + 1, r, s);
144 * We don't need both of these
153 private static void sortDouble(double[] arr, int p, int r, Object[] s)
159 q = partitionDouble(arr, p, r, s);
160 sortDouble(arr, p, q, s);
161 sortDouble(arr, q + 1, r, s);
165 private static void sortInt(int[] arr, int p, int r, Object[] s)
171 q = partitionInt(arr, p, r, s);
172 sortInt(arr, p, q, s);
173 sortInt(arr, q + 1, r, s);
177 private static int partitionFloat(float[] arr, int p, int r, Object[] s)
188 } while (arr[j] > x);
193 } while (arr[i] < x);
212 private static int partitionFloatChar(float[] arr, int p, int r, char[] s)
223 } while (arr[j] > x);
228 } while (arr[i] < x);
247 private static int partitionInt(int[] arr, int p, int r, Object[] s)
258 } while (arr[j] > x);
263 } while (arr[i] < x);
282 private static int partitionDouble(double[] arr, int p, int r, Object[] s)
293 } while (arr[j] > x);
298 } while (arr[i] < x);
317 private static int stringPartition(String[] arr, int p, int r, Object[] s)
328 } while (arr[j].compareTo(x) < 0);
333 } while (arr[i].compareTo(x) > 0);
353 * Sorts both arrays to give ascending order in the first array, by first
354 * partitioning into zero and non-zero values before sorting the latter.
359 public static void sortFloatChar(float[] arr, char[] s)
362 * Sort all zero values to the front
364 float[] f1 = new float[arr.length];
365 char[] s1 = new char[s.length];
366 int nextZeroValue = 0;
367 int nextNonZeroValue = arr.length - 1;
368 for (int i = 0; i < arr.length; i++)
373 f1[nextNonZeroValue] = val;
374 s1[nextNonZeroValue] = s[i];
379 f1[nextZeroValue] = val;
380 s1[nextZeroValue] = s[i];
386 * Copy zero values back to original arrays
388 System.arraycopy(f1, 0, arr, 0, nextZeroValue);
389 System.arraycopy(s1, 0, s, 0, nextZeroValue);
391 if (nextZeroValue == arr.length)
396 * Sort the non-zero values
398 float[] nonZeroFloats = Arrays
399 .copyOfRange(f1, nextZeroValue, f1.length);
400 char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
401 externalSortFloat(nonZeroFloats, nonZeroChars);
402 // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
405 * Assemble sorted non-zero results
407 System.arraycopy(nonZeroFloats, 0, arr, nextZeroValue,
408 nonZeroFloats.length);
409 System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
413 * Sort by making an array of indices, and sorting it using a comparator that
414 * refers to the float values.
417 * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
422 private static void externalSortFloat(float[] arr, char[] s)
424 final int length = arr.length;
425 Integer[] indices = makeIndexArray(length);
426 Arrays.sort(indices, new FloatComparator(arr));
429 * Copy the array values as per the sorted indices
431 float[] sortedFloats = new float[length];
432 char[] sortedChars = new char[s.length];
433 for (int i = 0; i < length; i++)
435 sortedFloats[i] = arr[indices[i]];
436 sortedChars[i] = s[indices[i]];
440 * And copy the sorted values back into the arrays
442 System.arraycopy(sortedFloats, 0, arr, 0, length);
443 System.arraycopy(sortedChars, 0, s, 0, s.length);
447 * Make an array whose values are 0...length.
452 private static Integer[] makeIndexArray(final int length)
454 Integer[] indices = new Integer[length];
455 for (int i = 0; i < length; i++)
462 // private static void sortFloat(float[] arr, int p, int r, char[] s)
467 // q = partitionFloatChar(arr, p, r, s);
468 // sortFloat(arr, p, q, s);
469 // sortFloat(arr, q + 1, r, s);
474 * Sorts both arrays to give ascending order in the first array, by first
475 * partitioning into zero and non-zero values before sorting the latter.
480 public static void sortIntChar(int[] arr, char[] s)
483 * Sort all zero values to the front
485 int[] f1 = new int[arr.length];
486 char[] s1 = new char[s.length];
487 int nextZeroValue = 0;
488 int nextNonZeroValue = arr.length - 1;
489 for (int i = 0; i < arr.length; i++)
494 f1[nextNonZeroValue] = val;
495 s1[nextNonZeroValue] = s[i];
500 f1[nextZeroValue] = val;
501 s1[nextZeroValue] = s[i];
507 * Copy zero values back to original arrays
509 System.arraycopy(f1, 0, arr, 0, nextZeroValue);
510 System.arraycopy(s1, 0, s, 0, nextZeroValue);
512 if (nextZeroValue == arr.length)
517 * Sort the non-zero values
519 int[] nonZeroInts = Arrays
520 .copyOfRange(f1, nextZeroValue, f1.length);
521 char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
522 externalSortInt(nonZeroInts, nonZeroChars);
523 // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
526 * Assemble sorted non-zero results
528 System.arraycopy(nonZeroInts, 0, arr, nextZeroValue, nonZeroInts.length);
529 System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
533 * Sort by making an array of indices, and sorting it using a comparator that
534 * refers to the float values.
537 * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
542 private static void externalSortInt(int[] arr, char[] s)
544 final int length = arr.length;
545 Integer[] indices = makeIndexArray(length);
546 Arrays.sort(indices, new IntComparator(arr));
549 * Copy the array values as per the sorted indices
551 int[] sortedInts = new int[length];
552 char[] sortedChars = new char[s.length];
553 for (int i = 0; i < length; i++)
555 sortedInts[i] = arr[indices[i]];
556 sortedChars[i] = s[indices[i]];
560 * And copy the sorted values back into the arrays
562 System.arraycopy(sortedInts, 0, arr, 0, length);
563 System.arraycopy(sortedChars, 0, s, 0, s.length);