SortTest.java - Testing Program

Sorting Algorithm Tutorials - Herong's Tutorial Examples

∟SortTest.java - Testing Program

This section describes a sample test program, SortTest.java, which can be used to test any sorting algorithm that is implemented under the Java API.

Here is my test program, SortTest.java, that runs sorting implementations with random data, and measures their execution performances:

/* SortTest.java
 * Copyright (c) 2011 HerongYang.com. All Rights Reserved.
 */
import java.util.*;
public class SortTest {
   static int arraySize = 10;
   static HyObject[] dataArray;
   static int numberOfTests = 1000;
   public static void main(String[] arg) {
      if (arg.length>0) arraySize = Integer.parseInt(arg[0]);
      if (arg.length>1) numberOfTests = Integer.parseInt(arg[1]);
      dataArray = new HyObject[arraySize];
      long sortTime = 0;
      Date startTime;
      for (int j=0; j<numberOfTests; j++) {
         HyObject.setRandom(j);
         for (int i=0; i<arraySize; i++) {
            dataArray[i] = new HyObject();
         }
         startTime = new Date();
         Arrays.sort(dataArray, 0, arraySize);
//       HyArrays.insertionSort(dataArray, 0, arraySize);
//       HyArrays.insertionSortImproved(dataArray, 0, arraySize);
//       HyArrays.selectionSort(dataArray, 0, arraySize);
//       HyArrays.bubbleSort(dataArray, 0, arraySize);
//       HyArrays.quickSort(dataArray, 0, arraySize);
//       HyArrays.quickSortImproved(dataArray, 0, arraySize);
//       HyArrays.quickSortAllison(dataArray, 0, arraySize);
//       HyArrays.mergeSort(dataArray, 0, arraySize);
//       HyArrays.mergeSort3(dataArray, 0, arraySize);
//       HyArrays.heapSort(dataArray, 0, arraySize);
//       HyArrays.shellSort(dataArray, 0, arraySize);
         sortTime += (new Date()).getTime() - startTime.getTime();
//       dump(dataArray, 0, arraySize);
      }
      sortTime = sortTime/numberOfTests;
      System.out.println("Array size: "+arraySize);
      System.out.println("Average sorting time: "+sortTime
         +" milliseconds");
      System.out.println("Number of tests: "+numberOfTests);
      printTimeInfo(sortTime, arraySize);
   }
   public static void printTimeInfo(long t, int n) {
      double nFactor = ((double)t)/(n/1000);
      double nnFactor = ((double)t)/((n/1000)*n);
      double log2n = Math.log((double) n)/Math.log(2.0);
      double ngFactor = ((double)t)/((n/1000)*log2n);
      System.out.println("Performance: "+nFactor
         +" O(N) microseconds");
      System.out.println("Performance: "+ngFactor
         +" O(N*Log2(N)) microseconds");
      System.out.println("Performance: "+nnFactor
         +" O(N*N) microseconds");
   }
   public static void dump(Object[] a, int fromIndex, int toIndex) {
      for (int i=fromIndex; i<toIndex; i++) {
         System.out.println("a["+i+"]: "+a[i].toString());
      }
   }
}

Note that:

I am repeating the sorting call 1000 times with randomly generated data elements each time to compute the average sorting time.
My own implementations of sorting algorithms are located in HyArrays class. The commented out statements represent calls to implementations of different sorting algorithms.
java.util.Arrays.sort() is a JDK implementation of Quicksort algorithm. It is used to demonstrate the test program.
The dump() method is provided just in case you want to verify if the data elements are really sorted.
The printTimeInfo() method shows how the implementation performs against 3 measuring scales: O(N), O(N*log2(N)), and O(N*N). I changed the unit of measure to microsecond to match the level of today's CPU power.

To verify this test program, I compiled and ran it as is with JDK 13. I did not see any issues.

herong> java -version
java version "13" 2019-09-17
Java(TM) SE Runtime Environment (build 13+33)
Java HotSpot(TM) 64-Bit Server VM (build 13+33, mixed mode, sharing)

herong> javac HyObject.java

herong> java SortTest.java
Array size: 10
Average sorting time: 0 milliseconds
Number of tests: 1000
Performance: NaN O(N) microseconds
Performance: NaN O(N*Log2(N)) microseconds
Performance: NaN O(N*N) microseconds

In case you are using older versions of Java that support only the raw "Comparable" interface type, here is my old test program, HyObjectOld.java:

/* SortTestOld.java
 * Copyright (c) 2008 HerongYang.com. All Rights Reserved.
 */
import java.util.*;
public class SortTestOld {
   static int arraySize = 10;
   static HyObjectOld[] dataArray;
   static int numberOfTests = 1000;
   public static void main(String[] arg) {
      if (arg.length>0) arraySize = Integer.parseInt(arg[0]);
      if (arg.length>1) numberOfTests = Integer.parseInt(arg[1]);
      dataArray = new HyObjectOld[arraySize];
      long sortTime = 0;
      Date startTime;
      for (int j=0; j<numberOfTests; j++) {
         HyObjectOld.setRandom(j);
         for (int i=0; i<arraySize; i++) {
            dataArray[i] = new HyObjectOld();
         }
         startTime = new Date();
         Arrays.sort(dataArray, 0, arraySize);
//       HyArraysOld.insertionSort(dataArray, 0, arraySize);
//       HyArraysOld.insertionSortImproved(dataArray, 0, arraySize);
//       HyArraysOld.selectionSort(dataArray, 0, arraySize);
//       HyArraysOld.bubbleSort(dataArray, 0, arraySize);
//       HyArraysOld.quickSort(dataArray, 0, arraySize);
//       HyArraysOld.quickSortImproved(dataArray, 0, arraySize);
//       HyArraysOld.quickSortAllison(dataArray, 0, arraySize);
//       HyArraysOld.mergeSort(dataArray, 0, arraySize);
//       HyArraysOld.mergeSort3(dataArray, 0, arraySize);
//       HyArraysOld.heapSort(dataArray, 0, arraySize);
//       HyArraysOld.shellSort(dataArray, 0, arraySize);
         sortTime += (new Date()).getTime() - startTime.getTime();
//       dump(dataArray, 0, arraySize);
      }
      sortTime = sortTime/numberOfTests;
      System.out.println("Array size: "+arraySize);
      System.out.println("Average sorting time: "+sortTime
         +" milliseconds");
      System.out.println("Number of tests: "+numberOfTests);
      printTimeInfo(sortTime, arraySize);
   }
   public static void printTimeInfo(long t, int n) {
      double nFactor = ((double)t)/(n/1000);
      double nnFactor = ((double)t)/((n/1000)*n);
      double log2n = Math.log((double) n)/Math.log(2.0);
      double ngFactor = ((double)t)/((n/1000)*log2n);
      System.out.println("Performance: "+nFactor
         +" O(N) microseconds");
      System.out.println("Performance: "+ngFactor
         +" O(N*Log2(N)) microseconds");
      System.out.println("Performance: "+nnFactor
         +" O(N*N) microseconds");
   }
   public static void dump(Object[] a, int fromIndex, int toIndex) {
      for (int i=fromIndex; i<toIndex; i++) {
         System.out.println("a["+i+"]: "+a[i].toString());
      }
   }
}