Timing the quick sort method

Question

I'm writing a program to compare different sorting algorithms speed. The majority of cases, I can begin each algorithms method with

long startTime = System.currentTimeMillis();

and end it with

long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime + " milliseconds");

However, because quick sort is recursive, this wont work as it'll print a time for every recursion, rather than the total elapsed time.

My Code

public static void quickSort(int[] arr, int low, int high) {

if (arr == null || arr.length == 0)
  return;

if (low >= high)
  return;

// pick the pivot
int middle = low + (high - low) / 2;
int pivot = arr[middle];

// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
  while (arr[i] < pivot) {
    i++;
  }

  while (arr[j] > pivot) {
    j--;
  }

  if (i <= j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    i++;
    j--;
  }
}

// recursively sort two sub parts
if (low < j)
  quickSort(arr, low, j);

if (high > i)
  quickSort(arr, i, high);

if ((low >= j) && (high <= i)) {




}


}

How can I make it so that it only runs "stopTime" the final iteration of the algorthim. Thanks

Be aware that using `System.currentTimeMillis` is not, generally, an actually good way to measure performance of algorithms. There's really very little way to get accurate, useful performance comparisons short of using a full benchmarking tool like JMH. — Louis Wasserman, Mar 13 '18 at 00:07
just wrap the quicksort method with another method. Then you can time from the top level inside the wrapping method. — Neil Locketz, Mar 13 '18 at 00:08

score -1 · Accepted Answer · answered Mar 13 '18 at 00:21

Don't measure the performance inside the recursive method. Either move the core code of the method in some private helper method or measure in the method where you call it, for example in your main method.

Helper method variant:

public static void quickSort(int[] arr, int low, int high) {
    long startTime = System.currentTimeMillis();

    // Call the helper
    quickSortHelper(arr, low, high);

    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println(elapsedTime + " milliseconds");
}

private static void quickSortHelper(int[] arr, int low, int high) {
    // All code goes here, adjust calls
    // to 'quickSort', they should now call 'quickSortHelper'
}

Be aware that your technique is just a quick way to get a rough estimate. There are numerous effects that will mess up your micro benchmarks if done like this. For example JVM noise (at startup) and especially caching effects (repeated calls to the method with same or similar input will be super fast since they are already cached).

You may read this question for more details: How do I write a correct micro-benchmark in Java?

Timing the quick sort method

1 Answers1