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(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
  62   public static void sort(double[] arr, int p, int r, Object[] s)
  63   {
  64     int q;
  65
  66     if (p < r)
  67     {
  68       q = partition(arr, p, r, s);
  69       sort(arr, p, q, s);
  70       sort(arr, q + 1, r, s);
  71     }
  72   }
  73
  74   private static int partition(float[] arr, int p, int r, Object[] s)
  75   {
  76     float x = arr[p];
  77     int i = p - 1;
  78     int j = r + 1;
  79
  80     while (true)
  81     {
  82       do
  83       {
  84         j = j - 1;
  85       } while (arr[j] > x);
  86
  87       do
  88       {
  89         i = i + 1;
  90       } while (arr[i] < x);
  91
  92       if (i < j)
  93       {
  94         float tmp = arr[i];
  95         arr[i] = arr[j];
  96         arr[j] = tmp;
  97
  98         Object tmp2 = s[i];
  99         s[i] = s[j];
 100         s[j] = tmp2;
 101       }
 102       else
 103       {
 104         return j;
 105       }
 106     }
 107   }
 108
 109   private static int partition(double[] arr, int p, int r, Object[] s)
 110   {
 111     double x = arr[p];
 112     int i = p - 1;
 113     int j = r + 1;
 114
 115     while (true)
 116     {
 117       do
 118       {
 119         j = j - 1;
 120       } while (arr[j] > x);
 121
 122       do
 123       {
 124         i = i + 1;
 125       } while (arr[i] < x);
 126
 127       if (i < j)
 128       {
 129         double tmp = arr[i];
 130         arr[i] = arr[j];
 131         arr[j] = tmp;
 132
 133         Object tmp2 = s[i];
 134         s[i] = s[j];
 135         s[j] = tmp2;
 136       }
 137       else
 138       {
 139         return j;
 140       }
 141     }
 142   }
 143
 144   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 145   {
 146     String x = arr[p];
 147     int i = p - 1;
 148     int j = r + 1;
 149
 150     while (true)
 151     {
 152       do
 153       {
 154         j = j - 1;
 155       } while (arr[j].compareTo(x) < 0);
 156
 157       do
 158       {
 159         i = i + 1;
 160       } while (arr[i].compareTo(x) > 0);
 161
 162       if (i < j)
 163       {
 164         String tmp = arr[i];
 165         arr[i] = arr[j];
 166         arr[j] = tmp;
 167
 168         Object tmp2 = s[i];
 169         s[i] = s[j];
 170         s[j] = tmp2;
 171       }
 172       else
 173       {
 174         return j;
 175       }
 176     }
 177   }
 178 }