QuickSort.java

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