src/jalview/util/QuickSort.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8)
   3  * Copyright (C) 2012 J Procter, AM Waterhouse, LM Lui, J Engelhardt, G Barton, M Clamp, S Searle
   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 of the License, or (at your option) any later version.
  10  *
  11  * Jalview is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty
  13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14  * PURPOSE.  See the GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 package jalview.util;
  19
  20 public class QuickSort
  21 {
  22   public static void sort(int[] arr, Object[] s)
  23   {
  24     sort(arr, 0, arr.length - 1, s);
  25   }
  26
  27   public static void sort(float[] arr, Object[] s)
  28   {
  29     sort(arr, 0, arr.length - 1, s);
  30   }
  31
  32   public static void sort(double[] arr, Object[] s)
  33   {
  34     sort(arr, 0, arr.length - 1, s);
  35   }
  36
  37   public static void sort(String[] arr, Object[] s)
  38   {
  39     stringSort(arr, 0, arr.length - 1, s);
  40   }
  41
  42   public static void stringSort(String[] arr, int p, int r, Object[] s)
  43   {
  44     int q;
  45
  46     if (p < r)
  47     {
  48       q = stringPartition(arr, p, r, s);
  49       stringSort(arr, p, q, s);
  50       stringSort(arr, q + 1, r, s);
  51     }
  52   }
  53
  54   public static void sort(float[] arr, int p, int r, Object[] s)
  55   {
  56     int q;
  57
  58     if (p < r)
  59     {
  60       q = partition(arr, p, r, s);
  61       sort(arr, p, q, s);
  62       sort(arr, q + 1, r, s);
  63     }
  64   }
  65
  66   public static void sort(double[] arr, int p, int r, Object[] s)
  67   {
  68     int q;
  69
  70     if (p < r)
  71     {
  72       q = partition(arr, p, r, s);
  73       sort(arr, p, q, s);
  74       sort(arr, q + 1, r, s);
  75     }
  76   }
  77
  78   public static void sort(int[] arr, int p, int r, Object[] s)
  79   {
  80     int q;
  81
  82     if (p < r)
  83     {
  84       q = partition(arr, p, r, s);
  85       sort(arr, p, q, s);
  86       sort(arr, q + 1, r, s);
  87     }
  88   }
  89
  90   private static int partition(float[] arr, int p, int r, Object[] s)
  91   {
  92     float x = arr[p];
  93     int i = p - 1;
  94     int j = r + 1;
  95
  96     while (true)
  97     {
  98       do
  99       {
 100         j = j - 1;
 101       } while (arr[j] > x);
 102
 103       do
 104       {
 105         i = i + 1;
 106       } while (arr[i] < x);
 107
 108       if (i < j)
 109       {
 110         float tmp = arr[i];
 111         arr[i] = arr[j];
 112         arr[j] = tmp;
 113
 114         Object tmp2 = s[i];
 115         s[i] = s[j];
 116         s[j] = tmp2;
 117       }
 118       else
 119       {
 120         return j;
 121       }
 122     }
 123   }
 124
 125   private static int partition(int[] arr, int p, int r, Object[] s)
 126   {
 127     int x = arr[p];
 128     int i = p - 1;
 129     int j = r + 1;
 130
 131     while (true)
 132     {
 133       do
 134       {
 135         j = j - 1;
 136       } while (arr[j] > x);
 137
 138       do
 139       {
 140         i = i + 1;
 141       } while (arr[i] < x);
 142
 143       if (i < j)
 144       {
 145         int tmp = arr[i];
 146         arr[i] = arr[j];
 147         arr[j] = tmp;
 148
 149         Object tmp2 = s[i];
 150         s[i] = s[j];
 151         s[j] = tmp2;
 152       }
 153       else
 154       {
 155         return j;
 156       }
 157     }
 158   }
 159
 160   private static int partition(double[] arr, int p, int r, Object[] s)
 161   {
 162     double x = arr[p];
 163     int i = p - 1;
 164     int j = r + 1;
 165
 166     while (true)
 167     {
 168       do
 169       {
 170         j = j - 1;
 171       } while (arr[j] > x);
 172
 173       do
 174       {
 175         i = i + 1;
 176       } while (arr[i] < x);
 177
 178       if (i < j)
 179       {
 180         double tmp = arr[i];
 181         arr[i] = arr[j];
 182         arr[j] = tmp;
 183
 184         Object tmp2 = s[i];
 185         s[i] = s[j];
 186         s[j] = tmp2;
 187       }
 188       else
 189       {
 190         return j;
 191       }
 192     }
 193   }
 194
 195   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 196   {
 197     String x = arr[p];
 198     int i = p - 1;
 199     int j = r + 1;
 200
 201     while (true)
 202     {
 203       do
 204       {
 205         j = j - 1;
 206       } while (arr[j].compareTo(x) < 0);
 207
 208       do
 209       {
 210         i = i + 1;
 211       } while (arr[i].compareTo(x) > 0);
 212
 213       if (i < j)
 214       {
 215         String tmp = arr[i];
 216         arr[i] = arr[j];
 217         arr[j] = tmp;
 218
 219         Object tmp2 = s[i];
 220         s[i] = s[j];
 221         s[j] = tmp2;
 222       }
 223       else
 224       {
 225         return j;
 226       }
 227     }
 228   }
 229 }