src/jalview/util/QuickSort.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Development Version 2.4.1)
   3  * Copyright (C) 2009 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19 package jalview.util;
  20
  21 public class QuickSort
  22 {
  23   public static void sort(int[] arr, Object[] s)
  24   {
  25     sort(arr, 0, arr.length - 1, s);
  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   public static void sort(int[] arr, int p, int r, Object[] s)
  78   {
  79     int q;
  80
  81     if (p < r)
  82     {
  83       q = partition(arr, p, r, s);
  84       sort(arr, p, q, s);
  85       sort(arr, q + 1, r, s);
  86     }
  87   }
  88
  89   private static int partition(float[] arr, int p, int r, Object[] s)
  90   {
  91     float x = arr[p];
  92     int i = p - 1;
  93     int j = r + 1;
  94
  95     while (true)
  96     {
  97       do
  98       {
  99         j = j - 1;
 100       } while (arr[j] > x);
 101
 102       do
 103       {
 104         i = i + 1;
 105       } while (arr[i] < x);
 106
 107       if (i < j)
 108       {
 109         float tmp = arr[i];
 110         arr[i] = arr[j];
 111         arr[j] = tmp;
 112
 113         Object tmp2 = s[i];
 114         s[i] = s[j];
 115         s[j] = tmp2;
 116       }
 117       else
 118       {
 119         return j;
 120       }
 121     }
 122   }
 123
 124   private static int partition(int[] arr, int p, int r, Object[] s)
 125   {
 126     int x = arr[p];
 127     int i = p - 1;
 128     int j = r + 1;
 129
 130     while (true)
 131     {
 132       do
 133       {
 134         j = j - 1;
 135       } while (arr[j] > x);
 136
 137       do
 138       {
 139         i = i + 1;
 140       } while (arr[i] < x);
 141
 142       if (i < j)
 143       {
 144         int tmp = arr[i];
 145         arr[i] = arr[j];
 146         arr[j] = tmp;
 147
 148         Object tmp2 = s[i];
 149         s[i] = s[j];
 150         s[j] = tmp2;
 151       }
 152       else
 153       {
 154         return j;
 155       }
 156     }
 157   }
 158
 159   private static int partition(double[] arr, int p, int r, Object[] s)
 160   {
 161     double x = arr[p];
 162     int i = p - 1;
 163     int j = r + 1;
 164
 165     while (true)
 166     {
 167       do
 168       {
 169         j = j - 1;
 170       } while (arr[j] > x);
 171
 172       do
 173       {
 174         i = i + 1;
 175       } while (arr[i] < x);
 176
 177       if (i < j)
 178       {
 179         double tmp = arr[i];
 180         arr[i] = arr[j];
 181         arr[j] = tmp;
 182
 183         Object tmp2 = s[i];
 184         s[i] = s[j];
 185         s[j] = tmp2;
 186       }
 187       else
 188       {
 189         return j;
 190       }
 191     }
 192   }
 193
 194   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 195   {
 196     String x = arr[p];
 197     int i = p - 1;
 198     int j = r + 1;
 199
 200     while (true)
 201     {
 202       do
 203       {
 204         j = j - 1;
 205       } while (arr[j].compareTo(x) < 0);
 206
 207       do
 208       {
 209         i = i + 1;
 210       } while (arr[i].compareTo(x) > 0);
 211
 212       if (i < j)
 213       {
 214         String tmp = arr[i];
 215         arr[i] = arr[j];
 216         arr[j] = tmp;
 217
 218         Object tmp2 = s[i];
 219         s[i] = s[j];
 220         s[j] = tmp2;
 221       }
 222       else
 223       {
 224         return j;
 225       }
 226     }
 227   }
 228 }