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 jalview.gui.JvOptionPane;
28 import java.util.Arrays;
29 import java.util.Random;
31 import org.testng.annotations.BeforeClass;
32 import org.testng.annotations.Test;
34 public class QuickSortTest
37 @BeforeClass(alwaysRun = true)
38 public void setUpJvOptionPane()
40 JvOptionPane.setInteractiveMode(false);
41 JvOptionPane.setMockResponse(JvOptionPane.CANCEL_OPTION);
44 private static final String c1 = "Blue";
46 private static final String c2 = "Yellow";
48 private static final String c3 = "Orange";
50 private static final String c4 = "Green";
52 private static final String c5 = "Pink";
54 @Test(groups = { "Functional" })
55 public void testSort_byIntValues()
57 int[] values = new int[] { 3, 0, 4, 3, -1 };
58 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
60 QuickSort.sort(values, things);
61 assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
62 // note sort is not stable: c1/c4 are equal but get reordered
63 Object[] expect = new Object[] { c5, c2, c4, c1, c3 };
64 assertTrue(Arrays.equals(expect, things));
68 * Test the alternative sort objects by integer method
70 @Test(groups = { "Functional" })
71 public void testSortByInt()
73 int[] values = new int[] { 3, 0, 4, 3, -1 };
74 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
79 QuickSort.sortByInt(values, things, true);
80 assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
81 assertTrue(Arrays.equals(new Object[] { c5, c2, c1, c4, c3 }, things));
84 * resort descending; c1/c4 should not change order
86 QuickSort.sortByInt(values, things, false);
87 assertTrue(Arrays.equals(new int[] { 4, 3, 3, 0, -1 }, values));
88 assertTrue(Arrays.equals(new Object[] { c3, c1, c4, c2, c5 }, things));
91 @Test(groups = { "Functional" })
92 public void testSort_byFloatValues()
94 float[] values = new float[] { 3f, 0f, 4f, 3f, -1f };
95 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
96 QuickSort.sort(values, things);
97 assertTrue(Arrays.equals(new float[] { -1f, 0f, 3f, 3f, 4f }, 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));
102 @Test(groups = { "Functional" })
103 public void testSort_byDoubleValues()
105 double[] values = new double[] { 3d, 0d, 4d, 3d, -1d };
106 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
107 QuickSort.sort(values, things);
108 assertTrue(Arrays.equals(new double[] { -1d, 0d, 3d, 3d, 4d }, values));
109 // note sort is not stable: c1/c4 are equal but get reordered
110 assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
114 * Sort by String is descending order, case-sensitive
116 @Test(groups = { "Functional" })
117 public void testSort_byStringValues()
119 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
120 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
122 QuickSort.sort(values, things);
124 Arrays.equals(new String[]
125 { "lucy", "henry", "henry", "JOHN", "ALISON" }, values));
126 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
130 * Test whether sort is stable i.e. equal values retain their mutual ordering.
132 @Test(groups = { "Functional" }, enabled = false)
133 public void testSort_withDuplicates()
135 int[] values = new int[] { 3, 4, 2, 4, 1 };
136 Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
137 QuickSort.sort(values, letters);
138 assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
139 // this fails - do we care?
141 Arrays.equals(new Object[]
142 { "Z", "Y", "A", "X", "B" }, letters));
146 * Test of method that sorts chars by a float array
148 @Test(groups = { "Functional" })
149 public void testSort_charSortByFloat_mostlyZeroValues()
151 char[] residues = new char[64];
152 for (int i = 0; i < 64; i++)
154 residues[i] = (char) i;
156 float[] counts = new float[64];
160 QuickSort.sort(counts, residues);
161 assertEquals(62, residues[0]); // negative sorts to front
162 assertEquals(59, residues[62]); // 7 sorts to next-to-end
163 assertEquals(43, residues[63]); // 16 sorts to end
167 * Timing test - to be run manually as needed, not part of the automated
169 * It shows that the optimised sort is 3-4 times faster than the simple
170 * external sort if the data to be sorted is mostly zero, but slightly slower
171 * if the data is fully populated with non-zero values. Worst case for an
172 * array of size 256 is about 100 sorts per millisecond.
174 @Test(groups = { "Timing" }, enabled = false)
175 public void testSort_timingTest()
177 char[] residues = new char[256];
178 for (int i = 0; i < residues.length; i++)
180 residues[i] = (char) i;
182 float[] counts = new float[residues.length];
184 int iterations = 1000000;
187 * time it using optimised sort (of a mostly zero-filled array)
189 long start = System.currentTimeMillis();
190 for (int i = 0; i < iterations; i++)
192 Arrays.fill(counts, 0f);
196 QuickSort.sort(counts, residues);
198 long elapsed = System.currentTimeMillis() - start;
199 System.out.println(String.format(
200 "Time for %d optimised sorts of mostly zeros array length %d was %dms",
201 iterations, counts.length, elapsed));
204 * time it using unoptimised external sort
206 start = System.currentTimeMillis();
207 for (int i = 0; i < iterations; i++)
209 Arrays.fill(counts, 0f);
213 QuickSort.charSortByFloat(counts, residues, true);
215 elapsed = System.currentTimeMillis() - start;
216 System.out.println(String.format(
217 "Time for %d external sorts of mostly zeros array length %d was %dms",
218 iterations, counts.length, elapsed));
221 * optimised external sort, well-filled array
223 Random random = new Random();
224 float[] randoms = new float[counts.length];
225 for (int i = 0; i < randoms.length; i++)
227 randoms[i] = random.nextFloat();
230 start = System.currentTimeMillis();
231 for (int i = 0; i < iterations; i++)
233 System.arraycopy(randoms, 0, counts, 0, randoms.length);
234 QuickSort.sort(counts, residues);
236 elapsed = System.currentTimeMillis() - start;
237 System.out.println(String.format(
238 "Time for %d optimised sorts of non-zeros array length %d was %dms",
239 iterations, counts.length, elapsed));
242 * time unoptimised external sort, filled array
244 start = System.currentTimeMillis();
245 for (int i = 0; i < iterations; i++)
247 System.arraycopy(randoms, 0, counts, 0, randoms.length);
248 QuickSort.charSortByFloat(counts, residues, true);
250 elapsed = System.currentTimeMillis() - start;
251 System.out.println(String.format(
252 "Time for %d external sorts of non-zeros array length %d was %dms",
253 iterations, counts.length, elapsed));
257 * Test that exercises sort without any attempt at fancy optimisation
259 @Test(groups = { "Functional" })
260 public void testCharSortByFloat()
262 char[] residues = new char[64];
263 for (int i = 0; i < 64; i++)
265 residues[i] = (char) i;
267 float[] counts = new float[64];
275 QuickSort.charSortByFloat(counts, residues, true);
276 assertEquals(62, residues[0]);
277 assertEquals(59, residues[62]);
278 assertEquals(43, residues[63]);
283 QuickSort.charSortByFloat(counts, residues, false);
284 assertEquals(62, residues[63]);
285 assertEquals(59, residues[1]);
286 assertEquals(43, residues[0]);
290 * Test of method that sorts chars by an int array
292 @Test(groups = { "Functional" })
293 public void testSort_charSortByInt_mostlyZeroValues()
295 char[] residues = new char[64];
296 for (int i = 0; i < 64; i++)
298 residues[i] = (char) i;
300 int[] counts = new int[64];
304 QuickSort.sort(counts, residues);
305 assertEquals(62, residues[0]); // negative sorts to front
306 assertEquals(59, residues[62]); // 7 sorts to next-to-end
307 assertEquals(43, residues[63]); // 16 sorts to end
311 * Test that exercises sorting without any attempt at fancy optimisation.
313 @Test(groups = { "Functional" })
314 public void testCharSortByInt()
316 char[] residues = new char[64];
317 for (int i = 0; i < 64; i++)
319 residues[i] = (char) i;
321 int[] counts = new int[64];
329 QuickSort.charSortByInt(counts, residues, true);
330 assertEquals(62, residues[0]);
331 assertEquals(59, residues[62]);
332 assertEquals(43, residues[63]);
337 QuickSort.charSortByInt(counts, residues, false);
338 assertEquals(62, residues[63]);
339 assertEquals(59, residues[1]);
340 assertEquals(43, residues[0]);
344 * Tests the alternative method to sort bby String in descending order,
347 @Test(groups = { "Functional" })
348 public void testSortByString()
350 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
351 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
357 QuickSort.sortByString(values, things, false);
359 Arrays.equals(new String[]
360 { "lucy", "henry", "henry", "JOHN", "ALISON" }, values));
361 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
366 QuickSort.sortByString(values, things, true);
368 Arrays.equals(new String[]
369 { "ALISON", "JOHN", "henry", "henry", "lucy" }, values));
370 // sort is stable: c2/c4 do not swap order
371 assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));