Sorting API in Java

Part:   1  2 

(Continued from previous part...)

SortTest.java - My Testing Program

Here is my test program, SortTest.java:

/**
 * SortTest.java
 * Copyright (c) 1999 by Dr. Herong Yang
 */
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]);
      }
      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();
         HyArrays.mySort(dataArray, 0, arraySize);
//       Arrays.sort(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) nonaseconds");
      System.out.println("Performance: "+ngFactor
         +" O(N*Log2(N)) nonaseconds");
      System.out.println("Performance: "+nnFactor
         +" O(N*N) nonaseconds");
   }
   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 to compute the average sorting time.
• My own implementations of sorting algorithms are located in HyArrays class. mySort() will be replaced by the actualy method name of my implementations.
• java.util.Arrays.sort() is a JDK implementation of Quicksort algorithm. It is included, but commented out, for comparison purpose.
• 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 nonasecond to match the level of today's CPU power.

Part:   1  2 

This site Web