Measuring time of different sort methods

Question

I am writing code that is supposed to measure different sort times for different sort methods with arrays of a specific size and display the output time in a GUI. I have got it working for the most part but the program is not displaying the same result each time. For instance, it will say 0.2 milliseconds for one run and 0.1 for the next. I believe the problem is in the runSort() method. Could anybody help me? Here is the code:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.Random;
import java.util.Arrays;

public class Benchmarks extends JFrame
{
  private static int numberOfRuns = 20;

  private JTextField arraySizeInput, display;
  private String sortMethodNames[] =
  {"Selection Sort", "Insertion Sort", "Mergesort", "Quicksort", "Arrays.sort"};
  private JComboBox chooseSortMethod;

  private final long seed;
  private int arraySize;

// Constructor
   public Benchmarks()
  {

     super("Benchmarks");

     Container c = getContentPane();
     c.setLayout(new GridLayout(6, 1));

     c.add(new JLabel(" Array size: "));
     arraySizeInput = new JTextField(4);
     arraySizeInput.setText("1000");
     arraySizeInput.selectAll();
     c.add(arraySizeInput);

     chooseSortMethod = new JComboBox(sortMethodNames);
     c.add(chooseSortMethod);

     JButton run = new JButton("Run");
     run.addActionListener(new RunButtonListener());
     c.add(run);

     c.add(new JLabel(" Avg Time (milliseconds): "));

     display = new JTextField("   Ready");
     display.setBackground(Color.YELLOW);
     display.setEditable(false);
     c.add(display);

  // Use the same random number generator seed for all benchmarks
  //   in one run of this program:

     seed = System.currentTimeMillis();
  }

// Fills a[] with random numbers and sorts it using the sorting method
// specified in sortMethod:
//     1 -- Selection Sort
//     2 -- Insertion Sort
//     3 -- Mergesort
//     4 -- Quicksort
// This is repeated numberOfRuns times for better accuracy
// Returns the total time it took in milliseconds.
   private long runSort(double[] a, int sortMethod, int numberOfRuns)
  {
     long startTime;
     long endTime;
     long diffTime;  
     Random generator = new Random(seed);
     for(int i= a.length-1; i>0; i--)
     {
        a[i]= generator.nextDouble(); 
     }
     startTime= System.currentTimeMillis();

     switch(sortMethod) 
     {  
        case 1: //Selection Sort
           SelectionSort sel = new SelectionSort(); 
           sel.sort(a);
           break; 
        case 2: //Insertion Sort 
           InsertionSort nsert= new InsertionSort();
           nsert.sort(a); 
           break; 
        case 3: //Merge Sort 
           Mergesort merge = new Mergesort(); 
           merge.sort(a); 
           break; 
        case 4: // Quick Sort 
           Quicksort quick = new Quicksort();
           quick.sort(a); 
           break; 
     }
     endTime= System.currentTimeMillis();
     diffTime= endTime- startTime; 


     return  diffTime ;  
  }

// Handles Run button events
   private class RunButtonListener implements ActionListener
  {
      public void actionPerformed(ActionEvent e)
     {
        String inputStr = arraySizeInput.getText().trim();
        try
        {
           arraySize = Integer.parseInt(inputStr);
        }
            catch (NumberFormatException ex)
           {
              display.setText(" Invalid array size");
              arraySize = 0;
              return;
           }  

        if (arraySize <= 0)
        {
           display.setText(" Invalid array size");
           return;
        }

        if (arraySize <= 0)
           return;

        int sortMethod = chooseSortMethod.getSelectedIndex() + 1;
        double a[] = new double[arraySize];
        double avgTime = (double)runSort(a, sortMethod, numberOfRuns)
                                                      / numberOfRuns;
        display.setText(String.format("  %.2f", avgTime));

        arraySizeInput.selectAll();
        arraySizeInput.requestFocus();
        System.out.println("Array size = " + arraySize +
           " Runs = " + numberOfRuns + " " +
           sortMethodNames[sortMethod - 1] + " avg time: " + avgTime);

     }
  }

//************************************************************

   public static void main(String[] args)
  {
     numberOfRuns = 20;
     if (args.length > 0)
     {
        int n = -1;
        try
        {
           n = Integer.parseInt(args[0].trim());
        }
            catch (NumberFormatException ex)
           {
              System.out.println("Invalid command-line parameter");
              System.exit(1);
           }
        if (n > 0)
           numberOfRuns = n;
     }

     Benchmarks window = new Benchmarks();
     window.setBounds(300, 300, 180, 200);
     window.setDefaultCloseOperation(EXIT_ON_CLOSE);
     window.setVisible(true);
  }
}

Thank you for the help.

Answer 1

You are getting different results because of many minor factors, like how busy the computer is at the time. Also, System.currentTimeMillis() is inherently inaccurate; on some systems, 5 ms may be measured as 0 to 10 ms. To get better accuracy when measuring small amounts of time, you should use System.nanoTime(). Also, you should have nothing at all between measuring the start time and measuring the end time. That means no for or while loops, if statements, or switch statements.

Answer 2

What you try is simply not possible. You'll need a system with garanteed cpu time. But scheduling and different loads makes it impossible to get exact times. Additional the Java-Garbage collection and things like optimizing from the java enviroment changes your results. you could use a framework like junitbenchmark and let the code run multible times - but rembemer this will not give you a "really usable" result. It can help you to determ the speed of each algorithm in relation to each other.