src/jalview/util/QuickSort.java

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