src/jalview/util/QuickSort.java

   1 package jalview.util;\r
   2 \r
   3 \r
   4 public class QuickSort {\r
   5 \r
   6   public static void sort(float[] arr,Object[] s) {\r
   7     sort(arr,0,arr.length-1,s);\r
   8   }\r
   9 \r
  10   public static void sort(String[] arr,Object[] s) {\r
  11     stringSort(arr,0,arr.length-1,s);\r
  12   }\r
  13 \r
  14   public static void stringSort(String[] arr,int p, int r,Object[] s) {\r
  15     int q;\r
  16 \r
  17     if (p < r) {\r
  18       q = stringPartition(arr,p,r,s);\r
  19       stringSort(arr,p,q,s);\r
  20       stringSort(arr,q+1,r,s);\r
  21     }\r
  22   }\r
  23 \r
  24   public static void sort(float[] arr,int p, int r,Object[] s) {\r
  25     int q;\r
  26 \r
  27     if (p < r) {\r
  28       q = partition(arr,p,r,s);\r
  29       sort(arr,p,q,s);\r
  30       sort(arr,q+1,r,s);\r
  31     }\r
  32   }\r
  33 \r
  34   private static int partition(float[] arr, int p, int r,Object[] s) {\r
  35     float x = arr[p];\r
  36     int i = p-1;\r
  37     int j = r+1;\r
  38 \r
  39     while(true) {\r
  40       do {\r
  41         j = j-1;\r
  42       } while (arr[j] > x);\r
  43 \r
  44       do {\r
  45         i = i+1;\r
  46       } while (arr[i] < x);\r
  47 \r
  48       if ( i < j) {\r
  49         float tmp = arr[i];\r
  50         arr[i] = arr[j];\r
  51         arr[j] = tmp;\r
  52 \r
  53         Object tmp2 = s[i];\r
  54         s[i] = s[j];\r
  55         s[j] = tmp2;\r
  56       } else {\r
  57         return j;\r
  58       }\r
  59     }\r
  60   }\r
  61   private static int stringPartition(String[] arr, int p, int r,Object[] s) {\r
  62     String x = arr[p];\r
  63     int i = p-1;\r
  64     int j = r+1;\r
  65 \r
  66     while(true) {\r
  67       do {\r
  68         j = j-1;\r
  69       } while (arr[j].compareTo(x) < 0);\r
  70 \r
  71       do {\r
  72         i = i+1;\r
  73       } while (arr[i].compareTo(x) > 0);\r
  74 \r
  75       if ( i < j) {\r
  76         String tmp = arr[i];\r
  77         arr[i] = arr[j];\r
  78         arr[j] = tmp;\r
  79 \r
  80         Object tmp2 = s[i];\r
  81         s[i] = s[j];\r
  82         s[j] = tmp2;\r
  83       } else {\r
  84         return j;\r
  85       }\r
  86     }\r
  87   }\r
  88 }\r
  89 \r
  90 \r
  91 \r