test/jalview/util/QuickSortTest.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   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.
  11  *
  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.
  16  *
  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.
  20  */
  21 package jalview.util;
  22
  23 import static org.testng.AssertJUnit.assertEquals;
  24 import static org.testng.AssertJUnit.assertTrue;
  25
  26 import java.util.Arrays;
  27 import java.util.Random;
  28
  29 import org.testng.annotations.Test;
  30
  31 public class QuickSortTest
  32 {
  33   private static final String c1 = "Blue";
  34
  35   private static final String c2 = "Yellow";
  36
  37   private static final String c3 = "Orange";
  38
  39   private static final String c4 = "Green";
  40
  41   private static final String c5 = "Pink";
  42
  43   @Test(groups = { "Functional" })
  44   public void testSort_byIntValues()
  45   {
  46     int[] values = new int[] { 3, 0, 4, 3, -1 };
  47     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
  48
  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));
  54   }
  55
  56   /**
  57    * Test the alternative sort objects by integer method
  58    */
  59   @Test(groups = { "Functional" })
  60   public void testSortByInt()
  61   {
  62     int[] values = new int[] { 3, 0, 4, 3, -1 };
  63     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
  64
  65     /*
  66      * sort ascending
  67      */
  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));
  71
  72     /*
  73      * resort descending; c1/c4 should not change order
  74      */
  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));
  78   }
  79
  80   @Test(groups = { "Functional" })
  81   public void testSort_byFloatValues()
  82   {
  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));
  89   }
  90
  91   @Test(groups = { "Functional" })
  92   public void testSort_byDoubleValues()
  93   {
  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));
 100   }
 101
 102   /**
 103    * Sort by String is descending order, case-sensitive
 104    */
 105   @Test(groups = { "Functional" })
 106   public void testSort_byStringValues()
 107   {
 108     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 109     String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
 110         "ALISON" };
 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));
 115   }
 116
 117   /**
 118    * Test whether sort is stable i.e. equal values retain their mutual ordering.
 119    */
 120   @Test(groups = { "Functional" }, enabled = false)
 121   public void testSort_withDuplicates()
 122   {
 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" },
 129             letters));
 130   }
 131
 132   /**
 133    * Test of method that sorts chars by a float array
 134    */
 135   @Test(groups = { "Functional" })
 136   public void testSort_charSortByFloat_mostlyZeroValues()
 137   {
 138     char[] residues = new char[64];
 139     for (int i = 0; i < 64; i++)
 140     {
 141       residues[i] = (char) i;
 142     }
 143     float[] counts = new float[64];
 144     counts[43] = 16;
 145     counts[59] = 7;
 146     counts[62] = -2;
 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
 151   }
 152
 153   /**
 154    * Timing test - to be run manually as needed, not part of the automated
 155    * suite. <br>
 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.
 160    */
 161   @Test(groups = { "Timing" }, enabled = false)
 162   public void testSort_timingTest()
 163   {
 164     char[] residues = new char[256];
 165     for (int i = 0; i < residues.length; i++)
 166     {
 167       residues[i] = (char) i;
 168     }
 169     float[] counts = new float[residues.length];
 170
 171     int iterations = 1000000;
 172
 173     /*
 174      * time it using optimised sort (of a mostly zero-filled array)
 175      */
 176     long start = System.currentTimeMillis();
 177     for (int i = 0; i < iterations; i++)
 178     {
 179       Arrays.fill(counts, 0f);
 180       counts[43] = 16;
 181       counts[59] = 7;
 182       counts[62] = -2;
 183       QuickSort.sort(counts, residues);
 184     }
 185     long elapsed = System.currentTimeMillis() - start;
 186     System.out
 187             .println(String
 188                     .format("Time for %d optimised sorts of mostly zeros array length %d was %dms",
 189                             iterations, counts.length, elapsed));
 190
 191     /*
 192      * time it using unoptimised external sort
 193      */
 194     start = System.currentTimeMillis();
 195     for (int i = 0; i < iterations; i++)
 196     {
 197       Arrays.fill(counts, 0f);
 198       counts[43] = 16;
 199       counts[59] = 7;
 200       counts[62] = -2;
 201       QuickSort.charSortByFloat(counts, residues, true);
 202     }
 203     elapsed = System.currentTimeMillis() - start;
 204     System.out
 205             .println(String
 206                     .format("Time for %d external sorts of mostly zeros array length %d was %dms",
 207                             iterations, counts.length, elapsed));
 208
 209     /*
 210      * optimised external sort, well-filled array
 211      */
 212     Random random = new Random();
 213     float[] randoms = new float[counts.length];
 214     for (int i = 0; i < randoms.length; i++)
 215     {
 216       randoms[i] = random.nextFloat();
 217     }
 218
 219     start = System.currentTimeMillis();
 220     for (int i = 0; i < iterations; i++)
 221     {
 222       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 223       QuickSort.sort(counts, residues);
 224     }
 225     elapsed = System.currentTimeMillis() - start;
 226     System.out
 227             .println(String
 228                     .format("Time for %d optimised sorts of non-zeros array length %d was %dms",
 229                             iterations, counts.length, elapsed));
 230
 231     /*
 232      * time unoptimised external sort, filled array
 233      */
 234     start = System.currentTimeMillis();
 235     for (int i = 0; i < iterations; i++)
 236     {
 237       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 238       QuickSort.charSortByFloat(counts, residues, true);
 239     }
 240     elapsed = System.currentTimeMillis() - start;
 241     System.out
 242             .println(String
 243                     .format("Time for %d external sorts of non-zeros array length %d was %dms",
 244                             iterations, counts.length, elapsed));
 245   }
 246
 247   /**
 248    * Test that exercises sort without any attempt at fancy optimisation
 249    */
 250   @Test(groups = { "Functional" })
 251   public void testCharSortByFloat()
 252   {
 253     char[] residues = new char[64];
 254     for (int i = 0; i < 64; i++)
 255     {
 256       residues[i] = (char) i;
 257     }
 258     float[] counts = new float[64];
 259     counts[43] = 16;
 260     counts[59] = 7;
 261     counts[62] = -2;
 262
 263     /*
 264      * sort ascending
 265      */
 266     QuickSort.charSortByFloat(counts, residues, true);
 267     assertEquals(62, residues[0]);
 268     assertEquals(59, residues[62]);
 269     assertEquals(43, residues[63]);
 270
 271     /*
 272      * resort descending
 273      */
 274     QuickSort.charSortByFloat(counts, residues, false);
 275     assertEquals(62, residues[63]);
 276     assertEquals(59, residues[1]);
 277     assertEquals(43, residues[0]);
 278   }
 279
 280   /**
 281    * Test of method that sorts chars by an int array
 282    */
 283   @Test(groups = { "Functional" })
 284   public void testSort_charSortByInt_mostlyZeroValues()
 285   {
 286     char[] residues = new char[64];
 287     for (int i = 0; i < 64; i++)
 288     {
 289       residues[i] = (char) i;
 290     }
 291     int[] counts = new int[64];
 292     counts[43] = 16;
 293     counts[59] = 7;
 294     counts[62] = -2;
 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
 299   }
 300
 301   /**
 302    * Test that exercises sorting without any attempt at fancy optimisation.
 303    */
 304   @Test(groups = { "Functional" })
 305   public void testCharSortByInt()
 306   {
 307     char[] residues = new char[64];
 308     for (int i = 0; i < 64; i++)
 309     {
 310       residues[i] = (char) i;
 311     }
 312     int[] counts = new int[64];
 313     counts[43] = 16;
 314     counts[59] = 7;
 315     counts[62] = -2;
 316
 317     /*
 318      * sort ascending
 319      */
 320     QuickSort.charSortByInt(counts, residues, true);
 321     assertEquals(62, residues[0]);
 322     assertEquals(59, residues[62]);
 323     assertEquals(43, residues[63]);
 324
 325     /*
 326      * resort descending
 327      */
 328     QuickSort.charSortByInt(counts, residues, false);
 329     assertEquals(62, residues[63]);
 330     assertEquals(59, residues[1]);
 331     assertEquals(43, residues[0]);
 332   }
 333
 334   /**
 335    * Tests the alternative method to sort bby String in descending order,
 336    * case-sensitive
 337    */
 338   @Test(groups = { "Functional" })
 339   public void testSortByString()
 340   {
 341     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 342     String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
 343         "ALISON" };
 344
 345     /*
 346      * sort descending
 347      */
 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));
 352
 353     /*
 354      * resort ascending
 355      */
 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));
 361   }
 362 }