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",
113 "JOHN", "ALISON" }, values));
114 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
118 * Test whether sort is stable i.e. equal values retain their mutual ordering.
120 @Test(groups = { "Functional" }, enabled = false)
121 public void testSort_withDuplicates()
123 int[] values = new int[] { 3, 4, 2, 4, 1 };
124 Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
125 QuickSort.sort(values, letters);
126 assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
127 // this fails - do we care?
128 assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" },
133 * Test of method that sorts chars by a float array
135 @Test(groups = { "Functional" })
136 public void testSort_charSortByFloat_mostlyZeroValues()
138 char[] residues = new char[64];
139 for (int i = 0; i < 64; i++)
141 residues[i] = (char) i;
143 float[] counts = new float[64];
147 QuickSort.sort(counts, residues);
148 assertEquals(62, residues[0]); // negative sorts to front
149 assertEquals(59, residues[62]); // 7 sorts to next-to-end
150 assertEquals(43, residues[63]); // 16 sorts to end
154 * Timing test - to be run manually as needed, not part of the automated
156 * It shows that the optimised sort is 3-4 times faster than the simple
157 * external sort if the data to be sorted is mostly zero, but slightly slower
158 * if the data is fully populated with non-zero values. Worst case for an
159 * array of size 256 is about 100 sorts per millisecond.
161 @Test(groups = { "Timing" }, enabled = false)
162 public void testSort_timingTest()
164 char[] residues = new char[256];
165 for (int i = 0; i < residues.length; i++)
167 residues[i] = (char) i;
169 float[] counts = new float[residues.length];
171 int iterations = 1000000;
174 * time it using optimised sort (of a mostly zero-filled array)
176 long start = System.currentTimeMillis();
177 for (int i = 0; i < iterations; i++)
179 Arrays.fill(counts, 0f);
183 QuickSort.sort(counts, residues);
185 long elapsed = System.currentTimeMillis() - start;
188 .format("Time for %d optimised sorts of mostly zeros array length %d was %dms",
189 iterations, counts.length, elapsed));
192 * time it using unoptimised external sort
194 start = System.currentTimeMillis();
195 for (int i = 0; i < iterations; i++)
197 Arrays.fill(counts, 0f);
201 QuickSort.charSortByFloat(counts, residues, true);
203 elapsed = System.currentTimeMillis() - start;
206 .format("Time for %d external sorts of mostly zeros array length %d was %dms",
207 iterations, counts.length, elapsed));
210 * optimised external sort, well-filled array
212 Random random = new Random();
213 float[] randoms = new float[counts.length];
214 for (int i = 0; i < randoms.length; i++)
216 randoms[i] = random.nextFloat();
219 start = System.currentTimeMillis();
220 for (int i = 0; i < iterations; i++)
222 System.arraycopy(randoms, 0, counts, 0, randoms.length);
223 QuickSort.sort(counts, residues);
225 elapsed = System.currentTimeMillis() - start;
228 .format("Time for %d optimised sorts of non-zeros array length %d was %dms",
229 iterations, counts.length, elapsed));
232 * time unoptimised external sort, filled array
234 start = System.currentTimeMillis();
235 for (int i = 0; i < iterations; i++)
237 System.arraycopy(randoms, 0, counts, 0, randoms.length);
238 QuickSort.charSortByFloat(counts, residues, true);
240 elapsed = System.currentTimeMillis() - start;
243 .format("Time for %d external sorts of non-zeros array length %d was %dms",
244 iterations, counts.length, elapsed));
248 * Test that exercises sort without any attempt at fancy optimisation
250 @Test(groups = { "Functional" })
251 public void testCharSortByFloat()
253 char[] residues = new char[64];
254 for (int i = 0; i < 64; i++)
256 residues[i] = (char) i;
258 float[] counts = new float[64];
266 QuickSort.charSortByFloat(counts, residues, true);
267 assertEquals(62, residues[0]);
268 assertEquals(59, residues[62]);
269 assertEquals(43, residues[63]);
274 QuickSort.charSortByFloat(counts, residues, false);
275 assertEquals(62, residues[63]);
276 assertEquals(59, residues[1]);
277 assertEquals(43, residues[0]);
281 * Test of method that sorts chars by an int array
283 @Test(groups = { "Functional" })
284 public void testSort_charSortByInt_mostlyZeroValues()
286 char[] residues = new char[64];
287 for (int i = 0; i < 64; i++)
289 residues[i] = (char) i;
291 int[] counts = new int[64];
295 QuickSort.sort(counts, residues);
296 assertEquals(62, residues[0]); // negative sorts to front
297 assertEquals(59, residues[62]); // 7 sorts to next-to-end
298 assertEquals(43, residues[63]); // 16 sorts to end
302 * Test that exercises sorting without any attempt at fancy optimisation.
304 @Test(groups = { "Functional" })
305 public void testCharSortByInt()
307 char[] residues = new char[64];
308 for (int i = 0; i < 64; i++)
310 residues[i] = (char) i;
312 int[] counts = new int[64];
320 QuickSort.charSortByInt(counts, residues, true);
321 assertEquals(62, residues[0]);
322 assertEquals(59, residues[62]);
323 assertEquals(43, residues[63]);
328 QuickSort.charSortByInt(counts, residues, false);
329 assertEquals(62, residues[63]);
330 assertEquals(59, residues[1]);
331 assertEquals(43, residues[0]);
335 * Tests the alternative method to sort bby String in descending order,
338 @Test(groups = { "Functional" })
339 public void testSortByString()
341 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
342 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
348 QuickSort.sortByString(values, things, false);
349 assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
350 "JOHN", "ALISON" }, values));
351 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
356 QuickSort.sortByString(values, things, true);
357 assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry",
358 "henry", "lucy" }, values));
359 // sort is stable: c2/c4 do not swap order
360 assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));