src/jalview/util/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 /**
  24  * A class to perform efficient sorting of arrays of objects based on arrays of
  25  * scores or other attributes. For example, residues by frequency.
  26  *
  27  * @author gmcarstairs
  28  *
  29  */
  30 public class QuickSort
  31 {
  32   /**
  33    * Sorts both arrays with respect to ascending order of the items in the first
  34    * array.
  35    *
  36    * @param arr
  37    * @param s
  38    */
  39   public static void sort(int[] arr, Object[] s)
  40   {
  41     sort(arr, 0, arr.length - 1, s);
  42   }
  43
  44   /**
  45    * Sorts both arrays with respect to ascending order of the items in the first
  46    * array.
  47    *
  48    * @param arr
  49    * @param s
  50    */
  51   public static void sort(float[] arr, Object[] s)
  52   {
  53     sort(arr, 0, arr.length - 1, s);
  54   }
  55
  56   /**
  57    * Sorts both arrays with respect to ascending order of the items in the first
  58    * array.
  59    *
  60    * @param arr
  61    * @param s
  62    */
  63   public static void sort(double[] arr, Object[] s)
  64   {
  65     sort(arr, 0, arr.length - 1, s);
  66   }
  67
  68   /**
  69    * Sorts both arrays with respect to descending order of the items in the
  70    * first array.
  71    *
  72    * @param arr
  73    * @param s
  74    */
  75   public static void sort(String[] arr, Object[] s)
  76   {
  77     stringSort(arr, 0, arr.length - 1, s);
  78   }
  79
  80   static void stringSort(String[] arr, int p, int r, Object[] s)
  81   {
  82     int q;
  83
  84     if (p < r)
  85     {
  86       q = stringPartition(arr, p, r, s);
  87       stringSort(arr, p, q, s);
  88       stringSort(arr, q + 1, r, s);
  89     }
  90   }
  91
  92   static void sort(float[] arr, int p, int r, Object[] s)
  93   {
  94     int q;
  95
  96     if (p < r)
  97     {
  98       q = partition(arr, p, r, s);
  99       sort(arr, p, q, s);
 100       sort(arr, q + 1, r, s);
 101     }
 102   }
 103
 104   static void sort(double[] arr, int p, int r, Object[] s)
 105   {
 106     int q;
 107
 108     if (p < r)
 109     {
 110       q = partition(arr, p, r, s);
 111       sort(arr, p, q, s);
 112       sort(arr, q + 1, r, s);
 113     }
 114   }
 115
 116   static void sort(int[] arr, int p, int r, Object[] s)
 117   {
 118     int q;
 119
 120     if (p < r)
 121     {
 122       q = partition(arr, p, r, s);
 123       sort(arr, p, q, s);
 124       sort(arr, q + 1, r, s);
 125     }
 126   }
 127
 128   static int partition(float[] arr, int p, int r, Object[] s)
 129   {
 130     float x = arr[p];
 131     int i = p - 1;
 132     int j = r + 1;
 133
 134     while (true)
 135     {
 136       do
 137       {
 138         j = j - 1;
 139       } while (arr[j] > x);
 140
 141       do
 142       {
 143         i = i + 1;
 144       } while (arr[i] < x);
 145
 146       if (i < j)
 147       {
 148         float tmp = arr[i];
 149         arr[i] = arr[j];
 150         arr[j] = tmp;
 151
 152         Object tmp2 = s[i];
 153         s[i] = s[j];
 154         s[j] = tmp2;
 155       }
 156       else
 157       {
 158         return j;
 159       }
 160     }
 161   }
 162
 163   static int partition(int[] arr, int p, int r, Object[] s)
 164   {
 165     int x = arr[p];
 166     int i = p - 1;
 167     int j = r + 1;
 168
 169     while (true)
 170     {
 171       do
 172       {
 173         j = j - 1;
 174       } while (arr[j] > x);
 175
 176       do
 177       {
 178         i = i + 1;
 179       } while (arr[i] < x);
 180
 181       if (i < j)
 182       {
 183         int tmp = arr[i];
 184         arr[i] = arr[j];
 185         arr[j] = tmp;
 186
 187         Object tmp2 = s[i];
 188         s[i] = s[j];
 189         s[j] = tmp2;
 190       }
 191       else
 192       {
 193         return j;
 194       }
 195     }
 196   }
 197
 198   static int partition(double[] arr, int p, int r, Object[] s)
 199   {
 200     double x = arr[p];
 201     int i = p - 1;
 202     int j = r + 1;
 203
 204     while (true)
 205     {
 206       do
 207       {
 208         j = j - 1;
 209       } while (arr[j] > x);
 210
 211       do
 212       {
 213         i = i + 1;
 214       } while (arr[i] < x);
 215
 216       if (i < j)
 217       {
 218         double tmp = arr[i];
 219         arr[i] = arr[j];
 220         arr[j] = tmp;
 221
 222         Object tmp2 = s[i];
 223         s[i] = s[j];
 224         s[j] = tmp2;
 225       }
 226       else
 227       {
 228         return j;
 229       }
 230     }
 231   }
 232
 233   static int stringPartition(String[] arr, int p, int r, Object[] s)
 234   {
 235     String 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].compareTo(x) < 0);
 245
 246       do
 247       {
 248         i = i + 1;
 249       } while (arr[i].compareTo(x) > 0);
 250
 251       if (i < j)
 252       {
 253         String 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 }