From d616b0e1ac213a82591cece50ea25c5bfbfa865f Mon Sep 17 00:00:00 2001 From: gmungoc Date: Thu, 4 Feb 2016 14:41:35 +0000 Subject: [PATCH] JAL-2005 added (stable) sort methods parameterised by ascending/descending --- src/jalview/analysis/AlignmentSorter.java | 65 +++--- src/jalview/util/QuickSort.java | 338 +++++++++++++++++++++++------ test/jalview/util/QuickSortTest.java | 294 ++++++++++++++++++++++--- 3 files changed, 569 insertions(+), 128 deletions(-) diff --git a/src/jalview/analysis/AlignmentSorter.java b/src/jalview/analysis/AlignmentSorter.java index b810050..007d538 100755 --- a/src/jalview/analysis/AlignmentSorter.java +++ b/src/jalview/analysis/AlignmentSorter.java @@ -755,6 +755,7 @@ public class AlignmentSorter MessageManager .getString("error.implementation_error_sortbyfeature")); } + boolean ignoreScore = method != FEATURE_SCORE; StringBuffer scoreLabel = new StringBuffer(); scoreLabel.append(start + stop + method); @@ -769,6 +770,21 @@ public class AlignmentSorter { scoreLabel.append(groupLabels[i] == null ? "null" : groupLabels[i]); } + + /* + * if resorting the same feature, toggle sort order + */ + if (lastSortByFeatureScore == null + || !scoreLabel.toString().equals(lastSortByFeatureScore)) + { + sortByFeatureScoreAscending = true; + } + else + { + sortByFeatureScoreAscending = !sortByFeatureScoreAscending; + } + lastSortByFeatureScore = scoreLabel.toString(); + SequenceI[] seqs = alignment.getSequencesArray(); boolean[] hasScore = new boolean[seqs.length]; // per sequence score @@ -855,7 +871,7 @@ public class AlignmentSorter labs[l] = (fs[l].getDescription() != null ? fs[l] .getDescription() : fs[l].getType()); } - jalview.util.QuickSort.sort(labs, ((Object[]) feats[i])); + QuickSort.sort(labs, ((Object[]) feats[i])); } } if (hasScore[i]) @@ -898,32 +914,27 @@ public class AlignmentSorter } else { - int nf = (feats[i] == null) ? 0 - : ((SequenceFeature[]) feats[i]).length; - // System.err.println("Sorting on Score: seq "+seqs[i].getName()+ - // " Feats: "+nf+" Score : "+scores[i]); + // int nf = (feats[i] == null) ? 0 + // : ((SequenceFeature[]) feats[i]).length; + // // System.err.println("Sorting on Score: seq " + + // seqs[i].getName() + // + " Feats: " + nf + " Score : " + scores[i]); } } } - - jalview.util.QuickSort.sort(scores, seqs); + QuickSort.sortByDouble(scores, seqs, sortByFeatureScoreAscending); } else if (method == FEATURE_DENSITY) { - - // break ties between equivalent numbers for adjacent sequences by adding - // 1/Nseq*i on the original order - double fr = 0.9 / (1.0 * seqs.length); for (int i = 0; i < seqs.length; i++) { - double nf; - scores[i] = (0.05 + fr * i) - + (nf = ((feats[i] == null) ? 0.0 - : 1.0 * ((SequenceFeature[]) feats[i]).length)); + int featureCount = feats[i] == null ? 0 + : ((SequenceFeature[]) feats[i]).length; + scores[i] = featureCount; // System.err.println("Sorting on Density: seq "+seqs[i].getName()+ - // " Feats: "+nf+" Score : "+scores[i]); + // " Feats: "+featureCount+" Score : "+scores[i]); } - jalview.util.QuickSort.sort(scores, seqs); + QuickSort.sortByDouble(scores, seqs, sortByFeatureScoreAscending); } else { @@ -933,24 +944,8 @@ public class AlignmentSorter MessageManager.getString("error.not_yet_implemented")); } } - if (lastSortByFeatureScore == null - || !scoreLabel.toString().equals(lastSortByFeatureScore)) - { - sortByFeatureScoreAscending = true; - } - else - { - sortByFeatureScoreAscending = !sortByFeatureScoreAscending; - } - if (sortByFeatureScoreAscending) - { - setOrder(alignment, seqs); - } - else - { - setReverseOrder(alignment, seqs); - } - lastSortByFeatureScore = scoreLabel.toString(); + + setOrder(alignment, seqs); } } diff --git a/src/jalview/util/QuickSort.java b/src/jalview/util/QuickSort.java index 2b58095..c1ef153 100755 --- a/src/jalview/util/QuickSort.java +++ b/src/jalview/util/QuickSort.java @@ -32,40 +32,106 @@ import java.util.Comparator; */ public class QuickSort { + /** + * A comparator that compares two integers by comparing their respective + * indexed values in an array of floats + */ static class FloatComparator implements Comparator { - private final float[] values; - FloatComparator(float[] v) + private boolean ascending; + + FloatComparator(float[] v, boolean asc) { values = v; + ascending = asc; } @Override public int compare(Integer o1, Integer o2) { - return Float.compare(values[o1], values[o2]); + return ascending ? Float.compare(values[o1], values[o2]) : Float + .compare(values[o2], values[o1]); } + } + + /** + * A comparator that compares two integers by comparing their respective + * indexed values in an array of doubles + */ + static class DoubleComparator implements Comparator + { + private final double[] values; + private boolean ascending; + + DoubleComparator(double[] v, boolean asc) + { + values = v; + ascending = asc; + } + + @Override + public int compare(Integer o1, Integer o2) + { + if (ascending) + { + return Double.compare(values[o1], values[o2]); + } + else + { + return Double.compare(values[o2], values[o1]); + } + } } + /** + * A comparator that compares two integers by comparing their respective + * indexed values in an array of ints + */ static class IntComparator implements Comparator { - private final int[] values; - IntComparator(int[] v) + private boolean ascending; + + IntComparator(int[] v, boolean asc) { values = v; + ascending = asc; } @Override public int compare(Integer o1, Integer o2) { - return Integer.compare(values[o1], values[o2]); + return ascending ? Integer.compare(values[o1], values[o2]) : Integer + .compare(values[o2], values[o1]); } + } + + /** + * A comparator that compares two integers by comparing their respective + * indexed values in an array of comparable objects. + */ + static class ExternalComparator implements Comparator + { + private final Comparable[] values; + private boolean ascending; + + ExternalComparator(Comparable[] v, boolean asc) + { + values = v; + ascending = asc; + } + + @Override + public int compare(Integer o1, Integer o2) + { + return ascending ? values[o1].compareTo(values[o2]) : values[o2] + .compareTo(values[o1]); + } } /** @@ -106,7 +172,7 @@ public class QuickSort /** * Sorts both arrays with respect to descending order of the items in the - * first array. + * first array. The sorting is case-sensitive. * * @param arr * @param s @@ -340,8 +406,10 @@ public class QuickSort } /** - * Sorts both arrays to give ascending order in the first array, by first - * partitioning into zero and non-zero values before sorting the latter. + * Sorts both arrays to give ascending order by the first array, by first + * partitioning into zero and non-zero values before sorting the latter. This + * is faster than a direct call to charSortByFloat in the case where most of + * the array to be sorted is zero. * * @param arr * @param s @@ -349,71 +417,87 @@ public class QuickSort public static void sort(float[] arr, char[] s) { /* - * Sort all zero values to the front + * Move all zero values to the front, non-zero to the back, while counting + * negative values */ float[] f1 = new float[arr.length]; char[] s1 = new char[s.length]; - int nextZeroValue = 0; + int negativeCount = 0; + int zerosCount = 0; int nextNonZeroValue = arr.length - 1; for (int i = 0; i < arr.length; i++) { float val = arr[i]; - if (val > 0f) + if (val != 0f) { f1[nextNonZeroValue] = val; s1[nextNonZeroValue] = s[i]; nextNonZeroValue--; + if (val < 0f) + { + negativeCount++; + } } else { - f1[nextZeroValue] = val; - s1[nextZeroValue] = s[i]; - nextZeroValue++; + f1[zerosCount] = val; + s1[zerosCount] = s[i]; + zerosCount++; } } + int positiveCount = arr.length - zerosCount - negativeCount; - /* - * Copy zero values back to original arrays - */ - System.arraycopy(f1, 0, arr, 0, nextZeroValue); - System.arraycopy(s1, 0, s, 0, nextZeroValue); - - if (nextZeroValue == arr.length) + if (zerosCount == arr.length) { return; // all zero } + + /* + * sort the non-zero values + */ + float[] nonZeroFloats = Arrays.copyOfRange(f1, zerosCount, f1.length); + char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length); + charSortByFloat(nonZeroFloats, nonZeroChars, true); + /* - * Sort the non-zero values + * Backfill zero values to original arrays, after the space reserved for + * negatives */ - float[] nonZeroFloats = Arrays - .copyOfRange(f1, nextZeroValue, f1.length); - char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length); - externalSort(nonZeroFloats, nonZeroChars); - // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars); + System.arraycopy(f1, 0, arr, negativeCount, zerosCount); + System.arraycopy(s1, 0, s, negativeCount, zerosCount); /* - * Assemble sorted non-zero results + * Copy sorted negative values to the front of arr, s */ - System.arraycopy(nonZeroFloats, 0, arr, nextZeroValue, - nonZeroFloats.length); - System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length); + System.arraycopy(nonZeroFloats, 0, arr, 0, negativeCount); + System.arraycopy(nonZeroChars, 0, s, 0, negativeCount); + + /* + * Copy sorted positive values after the negatives and zeros + */ + System.arraycopy(nonZeroFloats, negativeCount, arr, negativeCount + + zerosCount, positiveCount); + System.arraycopy(nonZeroChars, negativeCount, s, negativeCount + + zerosCount, positiveCount); } /** - * Sort by making an array of indices, and sorting it using a comparator that - * refers to the float values. + * Sorts arrays of float and char by the float values, by making an array of + * indices, and sorting it using a comparator that refers to the float values. * * @see http * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- * after-sorting * @param arr * @param s + * @param ascending */ - protected static void externalSort(float[] arr, char[] s) + public static void charSortByFloat(float[] arr, char[] s, + boolean ascending) { final int length = arr.length; Integer[] indices = makeIndexArray(length); - Arrays.sort(indices, new FloatComparator(arr)); + Arrays.sort(indices, new FloatComparator(arr, ascending)); /* * Copy the array values as per the sorted indices @@ -462,77 +546,95 @@ public class QuickSort /** * Sorts both arrays to give ascending order in the first array, by first - * partitioning into zero and non-zero values before sorting the latter. + * partitioning into zero and non-zero values before sorting the latter. This + * is faster than a direct call to charSortByInt in the case where most of the + * array to be sorted is zero. * * @param arr * @param s */ public static void sort(int[] arr, char[] s) - { - /* - * Sort all zero values to the front + { /* + * Move all zero values to the front, non-zero to the back, while counting + * negative values */ int[] f1 = new int[arr.length]; char[] s1 = new char[s.length]; - int nextZeroValue = 0; + int negativeCount = 0; + int zerosCount = 0; int nextNonZeroValue = arr.length - 1; for (int i = 0; i < arr.length; i++) { int val = arr[i]; - if (val > 0f) + if (val != 0f) { f1[nextNonZeroValue] = val; s1[nextNonZeroValue] = s[i]; nextNonZeroValue--; + if (val < 0) + { + negativeCount++; + } } else { - f1[nextZeroValue] = val; - s1[nextZeroValue] = s[i]; - nextZeroValue++; + f1[zerosCount] = val; + s1[zerosCount] = s[i]; + zerosCount++; } } + int positiveCount = arr.length - zerosCount - negativeCount; - /* - * Copy zero values back to original arrays - */ - System.arraycopy(f1, 0, arr, 0, nextZeroValue); - System.arraycopy(s1, 0, s, 0, nextZeroValue); - - if (nextZeroValue == arr.length) + if (zerosCount == arr.length) { return; // all zero } + + /* + * sort the non-zero values + */ + int[] nonZeroInts = Arrays.copyOfRange(f1, zerosCount, f1.length); + char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length); + charSortByInt(nonZeroInts, nonZeroChars, true); + + /* + * Backfill zero values to original arrays, after the space reserved for + * negatives + */ + System.arraycopy(f1, 0, arr, negativeCount, zerosCount); + System.arraycopy(s1, 0, s, negativeCount, zerosCount); + /* - * Sort the non-zero values + * Copy sorted negative values to the front of arr, s */ - int[] nonZeroInts = Arrays.copyOfRange(f1, nextZeroValue, f1.length); - char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length); - externalSort(nonZeroInts, nonZeroChars); - // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars); + System.arraycopy(nonZeroInts, 0, arr, 0, negativeCount); + System.arraycopy(nonZeroChars, 0, s, 0, negativeCount); /* - * Assemble sorted non-zero results + * Copy sorted positive values after the negatives and zeros */ - System.arraycopy(nonZeroInts, 0, arr, nextZeroValue, nonZeroInts.length); - System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length); + System.arraycopy(nonZeroInts, negativeCount, arr, negativeCount + + zerosCount, positiveCount); + System.arraycopy(nonZeroChars, negativeCount, s, negativeCount + + zerosCount, positiveCount); } /** - * Sort by making an array of indices, and sorting it using a comparator that - * refers to the float values. + * Sorts arrays of int and char, by making an array of indices, and sorting it + * using a comparator that refers to the int values. * * @see http * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- * after-sorting * @param arr * @param s + * @param ascending */ - protected static void externalSort(int[] arr, char[] s) + public static void charSortByInt(int[] arr, char[] s, boolean ascending) { final int length = arr.length; Integer[] indices = makeIndexArray(length); - Arrays.sort(indices, new IntComparator(arr)); + Arrays.sort(indices, new IntComparator(arr, ascending)); /* * Copy the array values as per the sorted indices @@ -551,4 +653,112 @@ public class QuickSort System.arraycopy(sortedInts, 0, arr, 0, length); System.arraycopy(sortedChars, 0, s, 0, s.length); } + + /** + * Sorts arrays of int and Object, by making an array of indices, and sorting + * it using a comparator that refers to the int values. + * + * @see http + * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- + * after-sorting + * @param arr + * @param s + * @param ascending + */ + public static void sortByInt(int[] arr, Object[] s, boolean ascending) + { + final int length = arr.length; + Integer[] indices = makeIndexArray(length); + Arrays.sort(indices, new IntComparator(arr, ascending)); + + /* + * Copy the array values as per the sorted indices + */ + int[] sortedInts = new int[length]; + Object[] sortedObjects = new Object[s.length]; + for (int i = 0; i < length; i++) + { + sortedInts[i] = arr[indices[i]]; + sortedObjects[i] = s[indices[i]]; + } + + /* + * And copy the sorted values back into the arrays + */ + System.arraycopy(sortedInts, 0, arr, 0, length); + System.arraycopy(sortedObjects, 0, s, 0, s.length); + } + + /** + * Sorts arrays of String and Object, by making an array of indices, and + * sorting it using a comparator that refers to the String values. Both arrays + * are sorted by case-sensitive order of the string array values. + * + * @see http + * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- + * after-sorting + * @param arr + * @param s + * @param ascending + */ + public static void sortByString(String[] arr, Object[] s, + boolean ascending) + { + final int length = arr.length; + Integer[] indices = makeIndexArray(length); + Arrays.sort(indices, new ExternalComparator(arr, ascending)); + + /* + * Copy the array values as per the sorted indices + */ + String[] sortedStrings = new String[length]; + Object[] sortedObjects = new Object[s.length]; + for (int i = 0; i < length; i++) + { + sortedStrings[i] = arr[indices[i]]; + sortedObjects[i] = s[indices[i]]; + } + + /* + * And copy the sorted values back into the arrays + */ + System.arraycopy(sortedStrings, 0, arr, 0, length); + System.arraycopy(sortedObjects, 0, s, 0, s.length); + } + + /** + * Sorts arrays of double and Object, by making an array of indices, and + * sorting it using a comparator that refers to the double values. + * + * @see http + * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array- + * after-sorting + * @param arr + * @param s + * @param ascending + */ + public static void sortByDouble(double[] arr, Object[] s, + boolean ascending) + { + final int length = arr.length; + Integer[] indices = makeIndexArray(length); + Arrays.sort(indices, new DoubleComparator(arr, ascending)); + + /* + * Copy the array values as per the sorted indices + */ + double[] sortedDoubles = new double[length]; + Object[] sortedObjects = new Object[s.length]; + for (int i = 0; i < length; i++) + { + sortedDoubles[i] = arr[indices[i]]; + sortedObjects[i] = s[indices[i]]; + } + + /* + * And copy the sorted values back into the arrays + */ + System.arraycopy(sortedDoubles, 0, arr, 0, length); + System.arraycopy(sortedObjects, 0, s, 0, s.length); + } } diff --git a/test/jalview/util/QuickSortTest.java b/test/jalview/util/QuickSortTest.java index 31b683b..54e46a0 100644 --- a/test/jalview/util/QuickSortTest.java +++ b/test/jalview/util/QuickSortTest.java @@ -24,8 +24,8 @@ import static org.testng.AssertJUnit.assertEquals; import static org.testng.AssertJUnit.assertTrue; import java.util.Arrays; +import java.util.Random; -import org.testng.annotations.BeforeMethod; import org.testng.annotations.Test; public class QuickSortTest @@ -38,41 +38,65 @@ public class QuickSortTest private static final String c4 = "Green"; - private Object[] things; + private static final String c5 = "Pink"; - private final Object[] sortedThings = new Object[] { c4, c2, c1, c3 }; - - @BeforeMethod(alwaysRun = true) - public void setUp() + @Test(groups = { "Functional" }) + public void testSort_byIntValues() { - things = new Object[] { c1, c2, c3, c4 }; + int[] values = new int[] { 3, 0, 4, 3, -1 }; + Object[] things = new Object[] { c1, c2, c3, c4, c5 }; + + QuickSort.sort(values, things); + assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values)); + // note sort is not stable: c1/c4 are equal but get reordered + Object[] expect = new Object[] { c5, c2, c4, c1, c3 }; + assertTrue(Arrays.equals(expect, things)); } + /** + * Test the alternative sort objects by integer method + */ @Test(groups = { "Functional" }) - public void testSort_byIntValues() + public void testSortByInt() { - int[] values = new int[] { 3, 2, 4, 1 }; - QuickSort.sort(values, things); - assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4 }, values)); - assertTrue(Arrays.equals(sortedThings, things)); + int[] values = new int[] { 3, 0, 4, 3, -1 }; + Object[] things = new Object[] { c1, c2, c3, c4, c5 }; + + /* + * sort ascending + */ + QuickSort.sortByInt(values, things, true); + assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values)); + assertTrue(Arrays.equals(new Object[] { c5, c2, c1, c4, c3 }, things)); + + /* + * resort descending; c1/c4 should not change order + */ + QuickSort.sortByInt(values, things, false); + assertTrue(Arrays.equals(new int[] { 4, 3, 3, 0, -1 }, values)); + assertTrue(Arrays.equals(new Object[] { c3, c1, c4, c2, c5 }, things)); } @Test(groups = { "Functional" }) public void testSort_byFloatValues() { - float[] values = new float[] { 3f, 2f, 4f, 1f }; + float[] values = new float[] { 3f, 0f, 4f, 3f, -1f }; + Object[] things = new Object[] { c1, c2, c3, c4, c5 }; QuickSort.sort(values, things); - assertTrue(Arrays.equals(new float[] { 1f, 2f, 3f, 4f }, values)); - assertTrue(Arrays.equals(sortedThings, things)); + assertTrue(Arrays.equals(new float[] { -1f, 0f, 3f, 3f, 4f }, values)); + // note sort is not stable: c1/c4 are equal but get reordered + assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things)); } @Test(groups = { "Functional" }) public void testSort_byDoubleValues() { - double[] values = new double[] { 3d, 2d, 4d, 1d }; + double[] values = new double[] { 3d, 0d, 4d, 3d, -1d }; + Object[] things = new Object[] { c1, c2, c3, c4, c5 }; QuickSort.sort(values, things); - assertTrue(Arrays.equals(new double[] { 1d, 2d, 3d, 4d }, values)); - assertTrue(Arrays.equals(sortedThings, things)); + assertTrue(Arrays.equals(new double[] { -1d, 0d, 3d, 3d, 4d }, values)); + // note sort is not stable: c1/c4 are equal but get reordered + assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things)); } /** @@ -81,11 +105,14 @@ public class QuickSortTest @Test(groups = { "Functional" }) public void testSort_byStringValues() { - String[] values = new String[] { "JOHN", "henry", "lucy", "ALISON" }; + Object[] things = new Object[] { c1, c2, c3, c4, c5 }; + String[] values = new String[] { "JOHN", "henry", "lucy", "henry", + "ALISON" }; QuickSort.sort(values, things); - assertTrue(Arrays.equals(new String[] { "lucy", "henry", "JOHN", + assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry", + "JOHN", "ALISON" }, values)); - assertTrue(Arrays.equals(new Object[] { c3, c2, c1, c4 }, things)); + assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things)); } /** @@ -95,20 +122,19 @@ public class QuickSortTest public void testSort_withDuplicates() { int[] values = new int[] { 3, 4, 2, 4, 1 }; - Object[] things = new Object[] { "A", "X", "Y", "B", "Z" }; - QuickSort.sort(values, things); + Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" }; + QuickSort.sort(values, letters); assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values)); // this fails - do we care? assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" }, - things)); + letters)); } /** - * Test that exercises sort with a mostly zero-valued sortby array. May be of - * interest to check the sort algorithm is efficient. + * Test of method that sorts chars by a float array */ @Test(groups = { "Functional" }) - public void testSort_MostlyZeroValues() + public void testSort_charSortByFloat_mostlyZeroValues() { char[] residues = new char[64]; for (int i = 0; i < 64; i++) @@ -118,10 +144,220 @@ public class QuickSortTest float[] counts = new float[64]; counts[43] = 16; counts[59] = 7; - counts[62] = 2; + counts[62] = -2; QuickSort.sort(counts, residues); + 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.
+ * 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]); assertEquals(43, residues[63]); + + /* + * resort descending + */ + QuickSort.charSortByFloat(counts, residues, false); + assertEquals(62, residues[63]); + assertEquals(59, residues[1]); + assertEquals(43, residues[0]); + } + + /** + * Test of method that sorts chars by an int array + */ + @Test(groups = { "Functional" }) + public void testSort_charSortByInt_mostlyZeroValues() + { + char[] residues = new char[64]; + for (int i = 0; i < 64; i++) + { + residues[i] = (char) i; + } + int[] counts = new int[64]; + counts[43] = 16; + counts[59] = 7; + counts[62] = -2; + QuickSort.sort(counts, residues); + 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 + } + + /** + * Test that exercises sorting without any attempt at fancy optimisation. + */ + @Test(groups = { "Functional" }) + public void testCharSortByInt() + { + char[] residues = new char[64]; + for (int i = 0; i < 64; i++) + { + residues[i] = (char) i; + } + int[] counts = new int[64]; + counts[43] = 16; + counts[59] = 7; + counts[62] = -2; + + /* + * sort ascending + */ + QuickSort.charSortByInt(counts, residues, true); + assertEquals(62, residues[0]); assertEquals(59, residues[62]); - assertEquals(62, residues[61]); + assertEquals(43, residues[63]); + + /* + * resort descending + */ + QuickSort.charSortByInt(counts, residues, false); + assertEquals(62, residues[63]); + assertEquals(59, residues[1]); + assertEquals(43, residues[0]); + } + + /** + * Tests the alternative method to sort bby String in descending order, + * case-sensitive + */ + @Test(groups = { "Functional" }) + public void testSortByString() + { + Object[] things = new Object[] { c1, c2, c3, c4, c5 }; + String[] values = new String[] { "JOHN", "henry", "lucy", "henry", + "ALISON" }; + + /* + * sort descending + */ + QuickSort.sortByString(values, things, false); + assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry", + "JOHN", "ALISON" }, values)); + assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things)); + + /* + * resort ascending + */ + QuickSort.sortByString(values, things, true); + assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry", + "henry", "lucy" }, values)); + // sort is stable: c2/c4 do not swap order + assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things)); } } -- 1.7.10.2