src/jalview/util/QuickSort.java

   1 /*\r
   2  * Jalview - A Sequence Alignment Editor and Viewer\r
   3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
   4  *\r
   5  * This program is free software; you can redistribute it and/or\r
   6  * modify it under the terms of the GNU General Public License\r
   7  * as published by the Free Software Foundation; either version 2\r
   8  * of the License, or (at your option) any later version.\r
   9  *\r
  10  * This program is distributed in the hope that it will be useful,\r
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13  * GNU General Public License for more details.\r
  14  *\r
  15  * You should have received a copy of the GNU General Public License\r
  16  * along with this program; if not, write to the Free Software\r
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
  18  */\r
  19 package jalview.util;\r
  20 \r
  21 public class QuickSort\r
  22 {\r
  23   public static void sort(float[] arr, Object[] s)\r
  24   {\r
  25     sort(arr, 0, arr.length - 1, s);\r
  26   }\r
  27 \r
  28   public static void sort(String[] arr, Object[] s)\r
  29   {\r
  30     stringSort(arr, 0, arr.length - 1, s);\r
  31   }\r
  32 \r
  33   public static void stringSort(String[] arr, int p, int r, Object[] s)\r
  34   {\r
  35     int q;\r
  36 \r
  37     if (p < r)\r
  38     {\r
  39       q = stringPartition(arr, p, r, s);\r
  40       stringSort(arr, p, q, s);\r
  41       stringSort(arr, q + 1, r, s);\r
  42     }\r
  43   }\r
  44 \r
  45   public static void sort(float[] arr, int p, int r, Object[] s)\r
  46   {\r
  47     int q;\r
  48 \r
  49     if (p < r)\r
  50     {\r
  51       q = partition(arr, p, r, s);\r
  52       sort(arr, p, q, s);\r
  53       sort(arr, q + 1, r, s);\r
  54     }\r
  55   }\r
  56 \r
  57   private static int partition(float[] arr, int p, int r, Object[] s)\r
  58   {\r
  59     float x = arr[p];\r
  60     int i = p - 1;\r
  61     int j = r + 1;\r
  62 \r
  63     while (true)\r
  64     {\r
  65       do\r
  66       {\r
  67         j = j - 1;\r
  68       }\r
  69       while (arr[j] > x);\r
  70 \r
  71       do\r
  72       {\r
  73         i = i + 1;\r
  74       }\r
  75       while (arr[i] < x);\r
  76 \r
  77       if (i < j)\r
  78       {\r
  79         float tmp = arr[i];\r
  80         arr[i] = arr[j];\r
  81         arr[j] = tmp;\r
  82 \r
  83         Object tmp2 = s[i];\r
  84         s[i] = s[j];\r
  85         s[j] = tmp2;\r
  86       }\r
  87       else\r
  88       {\r
  89         return j;\r
  90       }\r
  91     }\r
  92   }\r
  93 \r
  94   private static int stringPartition(String[] arr, int p, int r, Object[] s)\r
  95   {\r
  96     String x = arr[p];\r
  97     int i = p - 1;\r
  98     int j = r + 1;\r
  99 \r
 100     while (true)\r
 101     {\r
 102       do\r
 103       {\r
 104         j = j - 1;\r
 105       }\r
 106       while (arr[j].compareTo(x) < 0);\r
 107 \r
 108       do\r
 109       {\r
 110         i = i + 1;\r
 111       }\r
 112       while (arr[i].compareTo(x) > 0);\r
 113 \r
 114       if (i < j)\r
 115       {\r
 116         String tmp = arr[i];\r
 117         arr[i] = arr[j];\r
 118         arr[j] = tmp;\r
 119 \r
 120         Object tmp2 = s[i];\r
 121         s[i] = s[j];\r
 122         s[j] = tmp2;\r
 123       }\r
 124       else\r
 125       {\r
 126         return j;\r
 127       }\r
 128     }\r
 129   }\r
 130 }\r