ensure lastSeq is refreshed if new feature added
[jalview.git] / src / jalview / util / QuickSort.java
1 /*\r
2  * Jalview - A Sequence Alignment Editor and Viewer\r
3  * Copyright (C) 2006 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