Sort_Test.php - Sorting Performance Test

Sorting Algorithm Tutorials - Herong's Tutorial Examples

∟Sorting Algorithms Implementations in PHP

∟Sort_Test.php - Sorting Performance Test

This section describes a sample test program, Sort_Test.php, which can be used to test any sorting algorithm for data elements stored an array in PHP language.

If you like to program in PHP language, you may want to try to implement sorting algorithms in PHP. Here is my example of the sorting algorithm test program in PHP:

<?php
#- Sort_Test.php
#- Copyright (c) 2015 HerongYang.com. All Rights Reserved.
#-
  include "Sort_Function.php";
  $arraySize = 10;
  $numberOfTests = 1000;
  if (count($argv)>1) $arraySize  = intval($argv[1]);
  if (count($argv)>2) $numberOfTests  = intval($argv[2]);

  $sortTime = 0;
  for ($j=0; $j<$numberOfTests; $j++) {
    $dataArray = array();
    for ($i=0; $i<$arraySize; $i++) {
      $dataArray[$i] = rand();
    }
    $startTime = round(microtime(true)*1000);
    sort($dataArray);
#    insertionSort($dataArray, 0, $arraySize);
#    selectionSort($dataArray, 0, $arraySize);
#    bubbleSort($dataArray, 0, $arraySize);
#    quickSort($dataArray, 0, $arraySize);
#    mergeSort($dataArray, 0, $arraySize);
#    heapSort($dataArray, 0, $arraySize);
#    shellSort($dataArray, 0, $arraySize);
#    var_dump($dataArray);
    $sortTime += round(microtime(true)*1000) - $startTime;
  }
  $sortTime = $sortTime/$numberOfTests;

  print("Array size: $arraySize\n");
  print("Average sorting time: $sortTime milliseconds\n");
  print("Number of tests: $numberOfTests\n");
  printTimeInfo($sortTime, $arraySize);

function printTimeInfo($t, $n) {
  $nFactor = floatval($t)/(floatval($n)/1000);
  $nnFactor = floatval($t)/((floatval($n)/1000)*$n);
  $log2n = log(floatval($n))/log(2.0);
  $ngFactor = floatval($t)/(($n/1000)*$log2n);
  print("Performance: $nFactor O(N) microseconds\n");
  print("Performance: $ngFactor O(N*Log2(N)) microseconds\n");
  print("Performance: $nnFactor O(N*N) microseconds\n");
}
?>

Note that:

I am repeating the sorting call 1000 times with randomly generated integers each time to compute the average sorting time.
The commented out function call statements represent implementations of different sorting algorithms provided in the included Sort_Functions.php script file.
sort() is a PHP built-in implementation of the Quicksort algorithm. It is used to provide a performance baseline.
The var_dump() statement is provided just in case you want to verify if the array 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).

Before implementing my own versions of different sorting algorithms, I used the above test program to get some performance results with the built-in sort() function provided by PHP 5.6. Here are the results:

herong. php -version
PHP 5.6.30 (cli) (built: Oct 29 2017 20:30:32)
Copyright (c) 1997-2016 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2016 Zend Technologies

herong> php Sort_Test.php 10000 100
  Array size: 10000
  Average sorting time: 2.95 milliseconds
  Number of tests: 100
  Performance: 0.295 O(N) microseconds
  Performance: 0.022200962180219 O(N*Log2(N)) microseconds
  Performance: 2.95E-5 O(N*N) microseconds

herong> php Sort_Test.php 20000 100
  Array size: 20000
  Average sorting time: 6.94 milliseconds
  Number of tests: 100
  Performance: 0.347 O(N) microseconds
  Performance: 0.024286603116163 O(N*Log2(N)) microseconds
  Performance: 1.735E-5 O(N*N) microseconds

herong$ php Sort_Test.php 30000 100
  Array size: 30000
  Average sorting time: 13.06 milliseconds
  Number of tests: 100
  Performance: 0.43533333333333 O(N) microseconds
  Performance: 0.029270681759528 O(N*Log2(N)) microseconds
  Performance: 1.4511111111111E-5 O(N*N) microseconds

herong> php Sort_Test.php 100000 10
  Array size: 100000
  Average sorting time: 74.9 milliseconds
  Number of tests: 10
  Performance: 0.749 O(N) microseconds
  Performance: 0.045094293350464 O(N*Log2(N)) microseconds
  Performance: 7.49E-6 O(N*N) microseconds

The result was not very impressive comparing the Java language. For example, the Java version took 25 milliseconds for array size of 100000, but the PHP version took 71 milliseconds for the same array size. So I lower the array size to 10000, 20000 and 30000 to build the performance baseline.

Array Size        10000   20000   30000   100000   200000   300000
----------        -----   -----   -----   ------   ------   ------
JDK Arrays.sort                               25       66      112
PHP sort()            3       7      13       75