src/jalview/util/QuickSort.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer
   3  * Copyright (C) 2007 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(float[] arr, Object[] s)
  24   {
  25     sort(arr, 0, arr.length - 1, s);
  26   }
  27
  28   public static void sort(double[] arr, Object[] s)
  29   {
  30     sort(arr, 0, arr.length - 1, s);
  31   }
  32
  33   public static void sort(String[] arr, Object[] s)
  34   {
  35     stringSort(arr, 0, arr.length - 1, s);
  36   }
  37
  38   public static void stringSort(String[] arr, int p, int r, Object[] s)
  39   {
  40     int q;
  41
  42     if (p < r)
  43     {
  44       q = stringPartition(arr, p, r, s);
  45       stringSort(arr, p, q, s);
  46       stringSort(arr, q + 1, r, s);
  47     }
  48   }
  49
  50   public static void sort(float[] arr, int p, int r, Object[] s)
  51   {
  52     int q;
  53
  54     if (p < r)
  55     {
  56       q = partition(arr, p, r, s);
  57       sort(arr, p, q, s);
  58       sort(arr, q + 1, r, s);
  59     }
  60   }
  61   public static void sort(double[] arr, int p, int r, Object[] s)
  62   {
  63     int q;
  64
  65     if (p < r)
  66     {
  67       q = partition(arr, p, r, s);
  68       sort(arr, p, q, s);
  69       sort(arr, q + 1, r, s);
  70     }
  71   }
  72
  73   private static int partition(float[] arr, int p, int r, Object[] s)
  74   {
  75     float x = arr[p];
  76     int i = p - 1;
  77     int j = r + 1;
  78
  79     while (true)
  80     {
  81       do
  82       {
  83         j = j - 1;
  84       }
  85       while (arr[j] > x);
  86
  87       do
  88       {
  89         i = i + 1;
  90       }
  91       while (arr[i] < x);
  92
  93       if (i < j)
  94       {
  95         float tmp = arr[i];
  96         arr[i] = arr[j];
  97         arr[j] = tmp;
  98
  99         Object tmp2 = s[i];
 100         s[i] = s[j];
 101         s[j] = tmp2;
 102       }
 103       else
 104       {
 105         return j;
 106       }
 107     }
 108   }
 109
 110   private static int partition(double[] arr, int p, int r, Object[] s)
 111   {
 112     double x = arr[p];
 113     int i = p - 1;
 114     int j = r + 1;
 115
 116     while (true)
 117     {
 118       do
 119       {
 120         j = j - 1;
 121       }
 122       while (arr[j] > x);
 123
 124       do
 125       {
 126         i = i + 1;
 127       }
 128       while (arr[i] < x);
 129
 130       if (i < j)
 131       {
 132         double tmp = arr[i];
 133         arr[i] = arr[j];
 134         arr[j] = tmp;
 135
 136         Object tmp2 = s[i];
 137         s[i] = s[j];
 138         s[j] = tmp2;
 139       }
 140       else
 141       {
 142         return j;
 143       }
 144     }
 145   }
 146
 147   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 148   {
 149     String x = arr[p];
 150     int i = p - 1;
 151     int j = r + 1;
 152
 153     while (true)
 154     {
 155       do
 156       {
 157         j = j - 1;
 158       }
 159       while (arr[j].compareTo(x) < 0);
 160
 161       do
 162       {
 163         i = i + 1;
 164       }
 165       while (arr[i].compareTo(x) > 0);
 166
 167       if (i < j)
 168       {
 169         String tmp = arr[i];
 170         arr[i] = arr[j];
 171         arr[j] = tmp;
 172
 173         Object tmp2 = s[i];
 174         s[i] = s[j];
 175         s[j] = tmp2;
 176       }
 177       else
 178       {
 179         return j;
 180       }
 181     }
 182   }
 183 }