src/jalview/util/QuickSort.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.2b1)
   3  * Copyright (C) 2014 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 public class QuickSort
  24 {
  25   public static void sort(int[] arr, Object[] s)
  26   {
  27     sort(arr, 0, arr.length - 1, s);
  28   }
  29
  30   public static void sort(float[] arr, Object[] s)
  31   {
  32     sort(arr, 0, arr.length - 1, s);
  33   }
  34
  35   public static void sort(double[] arr, Object[] s)
  36   {
  37     sort(arr, 0, arr.length - 1, s);
  38   }
  39
  40   public static void sort(String[] arr, Object[] s)
  41   {
  42     stringSort(arr, 0, arr.length - 1, s);
  43   }
  44
  45   public static void stringSort(String[] arr, int p, int r, Object[] s)
  46   {
  47     int q;
  48
  49     if (p < r)
  50     {
  51       q = stringPartition(arr, p, r, s);
  52       stringSort(arr, p, q, s);
  53       stringSort(arr, q + 1, r, s);
  54     }
  55   }
  56
  57   public static void sort(float[] arr, int p, int r, Object[] s)
  58   {
  59     int q;
  60
  61     if (p < r)
  62     {
  63       q = partition(arr, p, r, s);
  64       sort(arr, p, q, s);
  65       sort(arr, q + 1, r, s);
  66     }
  67   }
  68
  69   public static void sort(double[] arr, int p, int r, Object[] s)
  70   {
  71     int q;
  72
  73     if (p < r)
  74     {
  75       q = partition(arr, p, r, s);
  76       sort(arr, p, q, s);
  77       sort(arr, q + 1, r, s);
  78     }
  79   }
  80
  81   public static void sort(int[] arr, int p, int r, Object[] s)
  82   {
  83     int q;
  84
  85     if (p < r)
  86     {
  87       q = partition(arr, p, r, s);
  88       sort(arr, p, q, s);
  89       sort(arr, q + 1, r, s);
  90     }
  91   }
  92
  93   private static int partition(float[] arr, int p, int r, Object[] s)
  94   {
  95     float x = arr[p];
  96     int i = p - 1;
  97     int j = r + 1;
  98
  99     while (true)
 100     {
 101       do
 102       {
 103         j = j - 1;
 104       } while (arr[j] > x);
 105
 106       do
 107       {
 108         i = i + 1;
 109       } while (arr[i] < x);
 110
 111       if (i < j)
 112       {
 113         float tmp = arr[i];
 114         arr[i] = arr[j];
 115         arr[j] = tmp;
 116
 117         Object tmp2 = s[i];
 118         s[i] = s[j];
 119         s[j] = tmp2;
 120       }
 121       else
 122       {
 123         return j;
 124       }
 125     }
 126   }
 127
 128   private static int partition(int[] arr, int p, int r, Object[] s)
 129   {
 130     int 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         int 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   private static int partition(double[] arr, int p, int r, Object[] s)
 164   {
 165     double 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         double 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   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 199   {
 200     String 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].compareTo(x) < 0);
 210
 211       do
 212       {
 213         i = i + 1;
 214       } while (arr[i].compareTo(x) > 0);
 215
 216       if (i < j)
 217       {
 218         String 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 }