+ assertEquals(62, residues[0]); // negative sorts to front
+ assertEquals(59, residues[62]); // 7 sorts to next-to-end
+ assertEquals(43, residues[63]); // 16 sorts to end
+ }
+
+ /**
+ * Timing test - to be run manually as needed, not part of the automated
+ * suite. <br>
+ * It shows that the optimised sort is 3-4 times faster than the simple
+ * external sort if the data to be sorted is mostly zero, but slightly slower
+ * if the data is fully populated with non-zero values. Worst case for an
+ * array of size 256 is about 100 sorts per millisecond.
+ */
+ @Test(groups = { "Timing" }, enabled = false)
+ public void testSort_timingTest()
+ {
+ char[] residues = new char[256];
+ for (int i = 0; i < residues.length; i++)
+ {
+ residues[i] = (char) i;
+ }
+ float[] counts = new float[residues.length];
+
+ int iterations = 1000000;
+
+ /*
+ * time it using optimised sort (of a mostly zero-filled array)
+ */
+ long start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ Arrays.fill(counts, 0f);
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+ QuickSort.sort(counts, residues);
+ }
+ long elapsed = System.currentTimeMillis() - start;
+ System.out.println(String.format(
+ "Time for %d optimised sorts of mostly zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+
+ /*
+ * time it using unoptimised external sort
+ */
+ start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ Arrays.fill(counts, 0f);
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+ QuickSort.charSortByFloat(counts, residues, true);
+ }
+ elapsed = System.currentTimeMillis() - start;
+ System.out.println(String.format(
+ "Time for %d external sorts of mostly zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+
+ /*
+ * optimised external sort, well-filled array
+ */
+ Random random = new Random();
+ float[] randoms = new float[counts.length];
+ for (int i = 0; i < randoms.length; i++)
+ {
+ randoms[i] = random.nextFloat();
+ }
+
+ start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ System.arraycopy(randoms, 0, counts, 0, randoms.length);
+ QuickSort.sort(counts, residues);
+ }
+ elapsed = System.currentTimeMillis() - start;
+ System.out.println(String.format(
+ "Time for %d optimised sorts of non-zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+
+ /*
+ * time unoptimised external sort, filled array
+ */
+ start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ System.arraycopy(randoms, 0, counts, 0, randoms.length);
+ QuickSort.charSortByFloat(counts, residues, true);
+ }
+ elapsed = System.currentTimeMillis() - start;
+ System.out.println(String.format(
+ "Time for %d external sorts of non-zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+ }
+
+ /**
+ * Test that exercises sort without any attempt at fancy optimisation
+ */
+ @Test(groups = { "Functional" })
+ public void testCharSortByFloat()
+ {
+ char[] residues = new char[64];
+ for (int i = 0; i < 64; i++)
+ {
+ residues[i] = (char) i;
+ }
+ float[] counts = new float[64];
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+
+ /*
+ * sort ascending
+ */
+ QuickSort.charSortByFloat(counts, residues, true);
+ assertEquals(62, residues[0]);
+ assertEquals(59, residues[62]);