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",
 114         "ALISON" }, values));
 115     assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
 116   }
 117
 118   /**
 119    * Test whether sort is stable i.e. equal values retain their mutual ordering.
 120    */
 121   @Test(groups = { "Functional" }, enabled = false)
 122   public void testSort_withDuplicates()
 123   {
 124     int[] values = new int[] { 3, 4, 2, 4, 1 };
 125     Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
 126     QuickSort.sort(values, letters);
 127     assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
 128     // this fails - do we care?
 129     assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" },
 130             letters));
 131   }
 132
 133   /**
 134    * Test of method that sorts chars by a float array
 135    */
 136   @Test(groups = { "Functional" })
 137   public void testSort_charSortByFloat_mostlyZeroValues()
 138   {
 139     char[] residues = new char[64];
 140     for (int i = 0; i < 64; i++)
 141     {
 142       residues[i] = (char) i;
 143     }
 144     float[] counts = new float[64];
 145     counts[43] = 16;
 146     counts[59] = 7;
 147     counts[62] = -2;
 148     QuickSort.sort(counts, residues);
 149     assertEquals(62, residues[0]); // negative sorts to front
 150     assertEquals(59, residues[62]); // 7 sorts to next-to-end
 151     assertEquals(43, residues[63]); // 16 sorts to end
 152   }
 153
 154   /**
 155    * Timing test - to be run manually as needed, not part of the automated
 156    * suite. <br>
 157    * It shows that the optimised sort is 3-4 times faster than the simple
 158    * external sort if the data to be sorted is mostly zero, but slightly slower
 159    * if the data is fully populated with non-zero values. Worst case for an
 160    * array of size 256 is about 100 sorts per millisecond.
 161    */
 162   @Test(groups = { "Timing" }, enabled = false)
 163   public void testSort_timingTest()
 164   {
 165     char[] residues = new char[256];
 166     for (int i = 0; i < residues.length; i++)
 167     {
 168       residues[i] = (char) i;
 169     }
 170     float[] counts = new float[residues.length];
 171
 172     int iterations = 1000000;
 173
 174     /*
 175      * time it using optimised sort (of a mostly zero-filled array)
 176      */
 177     long start = System.currentTimeMillis();
 178     for (int i = 0; i < iterations; i++)
 179     {
 180       Arrays.fill(counts, 0f);
 181       counts[43] = 16;
 182       counts[59] = 7;
 183       counts[62] = -2;
 184       QuickSort.sort(counts, residues);
 185     }
 186     long elapsed = System.currentTimeMillis() - start;
 187     System.out
 188             .println(String
 189                     .format("Time for %d optimised sorts of mostly zeros array length %d was %dms",
 190                             iterations, counts.length, elapsed));
 191
 192     /*
 193      * time it using unoptimised external sort
 194      */
 195     start = System.currentTimeMillis();
 196     for (int i = 0; i < iterations; i++)
 197     {
 198       Arrays.fill(counts, 0f);
 199       counts[43] = 16;
 200       counts[59] = 7;
 201       counts[62] = -2;
 202       QuickSort.charSortByFloat(counts, residues, true);
 203     }
 204     elapsed = System.currentTimeMillis() - start;
 205     System.out
 206             .println(String
 207                     .format("Time for %d external sorts of mostly zeros array length %d was %dms",
 208                             iterations, counts.length, elapsed));
 209
 210     /*
 211      * optimised external sort, well-filled array
 212      */
 213     Random random = new Random();
 214     float[] randoms = new float[counts.length];
 215     for (int i = 0; i < randoms.length; i++)
 216     {
 217       randoms[i] = random.nextFloat();
 218     }
 219
 220     start = System.currentTimeMillis();
 221     for (int i = 0; i < iterations; i++)
 222     {
 223       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 224       QuickSort.sort(counts, residues);
 225     }
 226     elapsed = System.currentTimeMillis() - start;
 227     System.out
 228             .println(String
 229                     .format("Time for %d optimised sorts of non-zeros array length %d was %dms",
 230                             iterations, counts.length, elapsed));
 231
 232     /*
 233      * time unoptimised external sort, filled array
 234      */
 235     start = System.currentTimeMillis();
 236     for (int i = 0; i < iterations; i++)
 237     {
 238       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 239       QuickSort.charSortByFloat(counts, residues, true);
 240     }
 241     elapsed = System.currentTimeMillis() - start;
 242     System.out
 243             .println(String
 244                     .format("Time for %d external sorts of non-zeros array length %d was %dms",
 245                             iterations, counts.length, elapsed));
 246   }
 247
 248   /**
 249    * Test that exercises sort without any attempt at fancy optimisation
 250    */
 251   @Test(groups = { "Functional" })
 252   public void testCharSortByFloat()
 253   {
 254     char[] residues = new char[64];
 255     for (int i = 0; i < 64; i++)
 256     {
 257       residues[i] = (char) i;
 258     }
 259     float[] counts = new float[64];
 260     counts[43] = 16;
 261     counts[59] = 7;
 262     counts[62] = -2;
 263
 264     /*
 265      * sort ascending
 266      */
 267     QuickSort.charSortByFloat(counts, residues, true);
 268     assertEquals(62, residues[0]);
 269     assertEquals(59, residues[62]);
 270     assertEquals(43, residues[63]);
 271
 272     /*
 273      * resort descending
 274      */
 275     QuickSort.charSortByFloat(counts, residues, false);
 276     assertEquals(62, residues[63]);
 277     assertEquals(59, residues[1]);
 278     assertEquals(43, residues[0]);
 279   }
 280
 281   /**
 282    * Test of method that sorts chars by an int array
 283    */
 284   @Test(groups = { "Functional" })
 285   public void testSort_charSortByInt_mostlyZeroValues()
 286   {
 287     char[] residues = new char[64];
 288     for (int i = 0; i < 64; i++)
 289     {
 290       residues[i] = (char) i;
 291     }
 292     int[] counts = new int[64];
 293     counts[43] = 16;
 294     counts[59] = 7;
 295     counts[62] = -2;
 296     QuickSort.sort(counts, residues);
 297     assertEquals(62, residues[0]); // negative sorts to front
 298     assertEquals(59, residues[62]); // 7 sorts to next-to-end
 299     assertEquals(43, residues[63]); // 16 sorts to end
 300   }
 301
 302   /**
 303    * Test that exercises sorting without any attempt at fancy optimisation.
 304    */
 305   @Test(groups = { "Functional" })
 306   public void testCharSortByInt()
 307   {
 308     char[] residues = new char[64];
 309     for (int i = 0; i < 64; i++)
 310     {
 311       residues[i] = (char) i;
 312     }
 313     int[] counts = new int[64];
 314     counts[43] = 16;
 315     counts[59] = 7;
 316     counts[62] = -2;
 317
 318     /*
 319      * sort ascending
 320      */
 321     QuickSort.charSortByInt(counts, residues, true);
 322     assertEquals(62, residues[0]);
 323     assertEquals(59, residues[62]);
 324     assertEquals(43, residues[63]);
 325
 326     /*
 327      * resort descending
 328      */
 329     QuickSort.charSortByInt(counts, residues, false);
 330     assertEquals(62, residues[63]);
 331     assertEquals(59, residues[1]);
 332     assertEquals(43, residues[0]);
 333   }
 334
 335   /**
 336    * Tests the alternative method to sort bby String in descending order,
 337    * case-sensitive
 338    */
 339   @Test(groups = { "Functional" })
 340   public void testSortByString()
 341   {
 342     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 343     String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
 344         "ALISON" };
 345
 346     /*
 347      * sort descending
 348      */
 349     QuickSort.sortByString(values, things, false);
 350     assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
 351         "JOHN", "ALISON" }, values));
 352     assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
 353
 354     /*
 355      * resort ascending
 356      */
 357     QuickSort.sortByString(values, things, true);
 358     assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry",
 359         "henry", "lucy" }, values));
 360     // sort is stable: c2/c4 do not swap order
 361     assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));
 362   }
 363 }