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