2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
7 * Jalview is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation, either version 3
10 * of the License, or (at your option) any later version.
12 * Jalview is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty
14 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19 * The Jalview Authors are detailed in the 'AUTHORS' file.
23 import static org.testng.AssertJUnit.assertEquals;
24 import static org.testng.AssertJUnit.assertTrue;
26 import java.util.Arrays;
27 import java.util.Random;
29 import org.testng.annotations.Test;
31 public class QuickSortTest
33 private static final String c1 = "Blue";
35 private static final String c2 = "Yellow";
37 private static final String c3 = "Orange";
39 private static final String c4 = "Green";
41 private static final String c5 = "Pink";
43 @Test(groups = { "Functional" })
44 public void testSort_byIntValues()
46 int[] values = new int[] { 3, 0, 4, 3, -1 };
47 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
49 QuickSort.sort(values, things);
50 assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
51 // note sort is not stable: c1/c4 are equal but get reordered
52 Object[] expect = new Object[] { c5, c2, c4, c1, c3 };
53 assertTrue(Arrays.equals(expect, things));
57 * Test the alternative sort objects by integer method
59 @Test(groups = { "Functional" })
60 public void testSortByInt()
62 int[] values = new int[] { 3, 0, 4, 3, -1 };
63 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
68 QuickSort.sortByInt(values, things, true);
69 assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
70 assertTrue(Arrays.equals(new Object[] { c5, c2, c1, c4, c3 }, things));
73 * resort descending; c1/c4 should not change order
75 QuickSort.sortByInt(values, things, false);
76 assertTrue(Arrays.equals(new int[] { 4, 3, 3, 0, -1 }, values));
77 assertTrue(Arrays.equals(new Object[] { c3, c1, c4, c2, c5 }, things));
80 @Test(groups = { "Functional" })
81 public void testSort_byFloatValues()
83 float[] values = new float[] { 3f, 0f, 4f, 3f, -1f };
84 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
85 QuickSort.sort(values, things);
86 assertTrue(Arrays.equals(new float[] { -1f, 0f, 3f, 3f, 4f }, values));
87 // note sort is not stable: c1/c4 are equal but get reordered
88 assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
91 @Test(groups = { "Functional" })
92 public void testSort_byDoubleValues()
94 double[] values = new double[] { 3d, 0d, 4d, 3d, -1d };
95 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
96 QuickSort.sort(values, things);
97 assertTrue(Arrays.equals(new double[] { -1d, 0d, 3d, 3d, 4d }, values));
98 // note sort is not stable: c1/c4 are equal but get reordered
99 assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
103 * Sort by String is descending order, case-sensitive
105 @Test(groups = { "Functional" })
106 public void testSort_byStringValues()
108 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
109 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
111 QuickSort.sort(values, things);
112 assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
114 "ALISON" }, values));
115 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
119 * Test whether sort is stable i.e. equal values retain their mutual ordering.
121 @Test(groups = { "Functional" }, enabled = false)
122 public void testSort_withDuplicates()
124 int[] values = new int[] { 3, 4, 2, 4, 1 };
125 Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
126 QuickSort.sort(values, letters);
127 assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
128 // this fails - do we care?
129 assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" },
134 * Test of method that sorts chars by a float array
136 @Test(groups = { "Functional" })
137 public void testSort_charSortByFloat_mostlyZeroValues()
139 char[] residues = new char[64];
140 for (int i = 0; i < 64; i++)
142 residues[i] = (char) i;
144 float[] counts = new float[64];
148 QuickSort.sort(counts, residues);
149 assertEquals(62, residues[0]); // negative sorts to front
150 assertEquals(59, residues[62]); // 7 sorts to next-to-end
151 assertEquals(43, residues[63]); // 16 sorts to end
155 * Timing test - to be run manually as needed, not part of the automated
157 * It shows that the optimised sort is 3-4 times faster than the simple
158 * external sort if the data to be sorted is mostly zero, but slightly slower
159 * if the data is fully populated with non-zero values. Worst case for an
160 * array of size 256 is about 100 sorts per millisecond.
162 @Test(groups = { "Timing" }, enabled = false)
163 public void testSort_timingTest()
165 char[] residues = new char[256];
166 for (int i = 0; i < residues.length; i++)
168 residues[i] = (char) i;
170 float[] counts = new float[residues.length];
172 int iterations = 1000000;
175 * time it using optimised sort (of a mostly zero-filled array)
177 long start = System.currentTimeMillis();
178 for (int i = 0; i < iterations; i++)
180 Arrays.fill(counts, 0f);
184 QuickSort.sort(counts, residues);
186 long elapsed = System.currentTimeMillis() - start;
189 .format("Time for %d optimised sorts of mostly zeros array length %d was %dms",
190 iterations, counts.length, elapsed));
193 * time it using unoptimised external sort
195 start = System.currentTimeMillis();
196 for (int i = 0; i < iterations; i++)
198 Arrays.fill(counts, 0f);
202 QuickSort.charSortByFloat(counts, residues, true);
204 elapsed = System.currentTimeMillis() - start;
207 .format("Time for %d external sorts of mostly zeros array length %d was %dms",
208 iterations, counts.length, elapsed));
211 * optimised external sort, well-filled array
213 Random random = new Random();
214 float[] randoms = new float[counts.length];
215 for (int i = 0; i < randoms.length; i++)
217 randoms[i] = random.nextFloat();
220 start = System.currentTimeMillis();
221 for (int i = 0; i < iterations; i++)
223 System.arraycopy(randoms, 0, counts, 0, randoms.length);
224 QuickSort.sort(counts, residues);
226 elapsed = System.currentTimeMillis() - start;
229 .format("Time for %d optimised sorts of non-zeros array length %d was %dms",
230 iterations, counts.length, elapsed));
233 * time unoptimised external sort, filled array
235 start = System.currentTimeMillis();
236 for (int i = 0; i < iterations; i++)
238 System.arraycopy(randoms, 0, counts, 0, randoms.length);
239 QuickSort.charSortByFloat(counts, residues, true);
241 elapsed = System.currentTimeMillis() - start;
244 .format("Time for %d external sorts of non-zeros array length %d was %dms",
245 iterations, counts.length, elapsed));
249 * Test that exercises sort without any attempt at fancy optimisation
251 @Test(groups = { "Functional" })
252 public void testCharSortByFloat()
254 char[] residues = new char[64];
255 for (int i = 0; i < 64; i++)
257 residues[i] = (char) i;
259 float[] counts = new float[64];
267 QuickSort.charSortByFloat(counts, residues, true);
268 assertEquals(62, residues[0]);
269 assertEquals(59, residues[62]);
270 assertEquals(43, residues[63]);
275 QuickSort.charSortByFloat(counts, residues, false);
276 assertEquals(62, residues[63]);
277 assertEquals(59, residues[1]);
278 assertEquals(43, residues[0]);
282 * Test of method that sorts chars by an int array
284 @Test(groups = { "Functional" })
285 public void testSort_charSortByInt_mostlyZeroValues()
287 char[] residues = new char[64];
288 for (int i = 0; i < 64; i++)
290 residues[i] = (char) i;
292 int[] counts = new int[64];
296 QuickSort.sort(counts, residues);
297 assertEquals(62, residues[0]); // negative sorts to front
298 assertEquals(59, residues[62]); // 7 sorts to next-to-end
299 assertEquals(43, residues[63]); // 16 sorts to end
303 * Test that exercises sorting without any attempt at fancy optimisation.
305 @Test(groups = { "Functional" })
306 public void testCharSortByInt()
308 char[] residues = new char[64];
309 for (int i = 0; i < 64; i++)
311 residues[i] = (char) i;
313 int[] counts = new int[64];
321 QuickSort.charSortByInt(counts, residues, true);
322 assertEquals(62, residues[0]);
323 assertEquals(59, residues[62]);
324 assertEquals(43, residues[63]);
329 QuickSort.charSortByInt(counts, residues, false);
330 assertEquals(62, residues[63]);
331 assertEquals(59, residues[1]);
332 assertEquals(43, residues[0]);
336 * Tests the alternative method to sort bby String in descending order,
339 @Test(groups = { "Functional" })
340 public void testSortByString()
342 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
343 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
349 QuickSort.sortByString(values, things, false);
350 assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
351 "JOHN", "ALISON" }, values));
352 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
357 QuickSort.sortByString(values, things, true);
358 assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry",
359 "henry", "lucy" }, values));
360 // sort is stable: c2/c4 do not swap order
361 assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));