src/jalview/util/QuickSort.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.0b1)
   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 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  * The Jalview Authors are detailed in the 'AUTHORS' file.
  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
  28   public static void sort(float[] arr, Object[] s)
  29   {
  30     sort(arr, 0, arr.length - 1, s);
  31   }
  32
  33   public static void sort(double[] arr, Object[] s)
  34   {
  35     sort(arr, 0, arr.length - 1, s);
  36   }
  37
  38   public static void sort(String[] arr, Object[] s)
  39   {
  40     stringSort(arr, 0, arr.length - 1, s);
  41   }
  42
  43   public static void stringSort(String[] arr, int p, int r, Object[] s)
  44   {
  45     int q;
  46
  47     if (p < r)
  48     {
  49       q = stringPartition(arr, p, r, s);
  50       stringSort(arr, p, q, s);
  51       stringSort(arr, q + 1, r, s);
  52     }
  53   }
  54
  55   public static void sort(float[] arr, int p, int r, Object[] s)
  56   {
  57     int q;
  58
  59     if (p < r)
  60     {
  61       q = partition(arr, p, r, s);
  62       sort(arr, p, q, s);
  63       sort(arr, q + 1, r, s);
  64     }
  65   }
  66
  67   public static void sort(double[] arr, int p, int r, Object[] s)
  68   {
  69     int q;
  70
  71     if (p < r)
  72     {
  73       q = partition(arr, p, r, s);
  74       sort(arr, p, q, s);
  75       sort(arr, q + 1, r, s);
  76     }
  77   }
  78
  79   public static void sort(int[] arr, int p, int r, Object[] s)
  80   {
  81     int q;
  82
  83     if (p < r)
  84     {
  85       q = partition(arr, p, r, s);
  86       sort(arr, p, q, s);
  87       sort(arr, q + 1, r, s);
  88     }
  89   }
  90
  91   private static int partition(float[] arr, int p, int r, Object[] s)
  92   {
  93     float x = arr[p];
  94     int i = p - 1;
  95     int j = r + 1;
  96
  97     while (true)
  98     {
  99       do
 100       {
 101         j = j - 1;
 102       } while (arr[j] > x);
 103
 104       do
 105       {
 106         i = i + 1;
 107       } while (arr[i] < x);
 108
 109       if (i < j)
 110       {
 111         float tmp = arr[i];
 112         arr[i] = arr[j];
 113         arr[j] = tmp;
 114
 115         Object tmp2 = s[i];
 116         s[i] = s[j];
 117         s[j] = tmp2;
 118       }
 119       else
 120       {
 121         return j;
 122       }
 123     }
 124   }
 125
 126   private static int partition(int[] arr, int p, int r, Object[] s)
 127   {
 128     int x = arr[p];
 129     int i = p - 1;
 130     int j = r + 1;
 131
 132     while (true)
 133     {
 134       do
 135       {
 136         j = j - 1;
 137       } while (arr[j] > x);
 138
 139       do
 140       {
 141         i = i + 1;
 142       } while (arr[i] < x);
 143
 144       if (i < j)
 145       {
 146         int tmp = arr[i];
 147         arr[i] = arr[j];
 148         arr[j] = tmp;
 149
 150         Object tmp2 = s[i];
 151         s[i] = s[j];
 152         s[j] = tmp2;
 153       }
 154       else
 155       {
 156         return j;
 157       }
 158     }
 159   }
 160
 161   private static int partition(double[] arr, int p, int r, Object[] s)
 162   {
 163     double x = arr[p];
 164     int i = p - 1;
 165     int j = r + 1;
 166
 167     while (true)
 168     {
 169       do
 170       {
 171         j = j - 1;
 172       } while (arr[j] > x);
 173
 174       do
 175       {
 176         i = i + 1;
 177       } while (arr[i] < x);
 178
 179       if (i < j)
 180       {
 181         double tmp = arr[i];
 182         arr[i] = arr[j];
 183         arr[j] = tmp;
 184
 185         Object tmp2 = s[i];
 186         s[i] = s[j];
 187         s[j] = tmp2;
 188       }
 189       else
 190       {
 191         return j;
 192       }
 193     }
 194   }
 195
 196   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 197   {
 198     String x = arr[p];
 199     int i = p - 1;
 200     int j = r + 1;
 201
 202     while (true)
 203     {
 204       do
 205       {
 206         j = j - 1;
 207       } while (arr[j].compareTo(x) < 0);
 208
 209       do
 210       {
 211         i = i + 1;
 212       } while (arr[i].compareTo(x) > 0);
 213
 214       if (i < j)
 215       {
 216         String tmp = arr[i];
 217         arr[i] = arr[j];
 218         arr[j] = tmp;
 219
 220         Object tmp2 = s[i];
 221         s[i] = s[j];
 222         s[j] = tmp2;
 223       }
 224       else
 225       {
 226         return j;
 227       }
 228     }
 229   }
 230 }