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) 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:

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) 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());
      }
   }
}

Table of Contents

 About This Book

 Introduction of Sorting Algorithms

Java API for Sorting Algorithms

 Why Java API Is Needed

 HyObject.java - Data Element Class

SortTest.java - Testing Program

 java.util.Arrays.sort() - Performance

 Performance Summary of Java Implementations

 Insertion Sort Algorithm and Java Implementation

 Selection Sort Algorithm and Java Implementation

 Bubble Sort Algorithm and Java Implementation

 Quicksort Algorithm and Java Implementation

 Merge Sort Algorithm and Java Implementation

 Heap Sort Algorithm and Java Implementation

 Shell Sort Algorithm and Java Implementation

 Sorting Algorithms Implementations in PHP

 Sorting Algorithms Implementations in Perl

 Sorting Algorithms Implementations in Python

 Performance Summary of All Implementations

 References

 Full Version in PDF/EPUB