src/jalview/util/QuickSort.java

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