edainworks.com :: VGR :: Comparing various sorting algorithms in PHP for sample sizes 100, 1000 and 10000.

NOT displaying sorted results (you can trust me, they're sorted!)

original unsorted array (dimension=100) :
element 0 : value 4
element 1 : value 9
element 2 : value 4
element 3 : value 7
element 4 : value 4
element 5 : value 10
element 6 : value 8
element 7 : value 0
element 8 : value 3
element 9 : value 0
element 10 : value 3
element 11 : value 2
element 12 : value 8
element 13 : value 10
element 14 : value 10
element 15 : value 1
element 16 : value 6
element 17 : value 3
element 18 : value 9
element 19 : value 0
element 20 : value 0
element 21 : value 9
element 22 : value 2
element 23 : value 8
element 24 : value 8
element 25 : value 6
element 26 : value 10
element 27 : value 7
element 28 : value 9
element 29 : value 8
element 30 : value 6
element 31 : value 5
element 32 : value 9
element 33 : value 10
element 34 : value 5
element 35 : value 6
element 36 : value 4
element 37 : value 8
element 38 : value 5
element 39 : value 2
element 40 : value 10
element 41 : value 3
element 42 : value 9
element 43 : value 8
element 44 : value 6
element 45 : value 7
element 46 : value 6
element 47 : value 8
element 48 : value 1
element 49 : value 10
element 50 : value 4
element 51 : value 6
element 52 : value 5
element 53 : value 1
element 54 : value 5
element 55 : value 1
element 56 : value 7
element 57 : value 5
element 58 : value 4
element 59 : value 3
element 60 : value 2
element 61 : value 2
element 62 : value 0
element 63 : value 6
element 64 : value 4
element 65 : value 9
element 66 : value 9
element 67 : value 4
element 68 : value 9
element 69 : value 3
element 70 : value 2
element 71 : value 0
element 72 : value 3
element 73 : value 6
element 74 : value 0
element 75 : value 8
element 76 : value 2
element 77 : value 10
element 78 : value 9
element 79 : value 1
element 80 : value 6
element 81 : value 6
element 82 : value 0
element 83 : value 5
element 84 : value 5
element 85 : value 4
element 86 : value 5
element 87 : value 10
element 88 : value 5
element 89 : value 6
element 90 : value 10
element 91 : value 10
element 92 : value 5
element 93 : value 1
element 94 : value 2
element 95 : value 6
element 96 : value 5
element 97 : value 2
element 98 : value 4
element 99 : value 4

Instantaneous sort + display results
sorted array is :
[snip data]
time elapsed = 0.05412 ms

PHP built-in array_sort() functions)
sorted array is :
[snip data]
time elapsed = 0.02193 ms

InsertionSort()
sorted array is :
[snip data]
time elapsed = 0.22697 ms

QuickSort()
sorted array is :
[snip data]
time elapsed = 0.09203 ms

original unsorted array (dimension=1000) :
[snip data]

Instantaneous sort + display results
sorted array is :
[snip data]
time elapsed = 0.45705 ms

PHP built-in array_sort() functions)
sorted array is :
[snip data]
time elapsed = 0.16785 ms

InsertionSort()
sorted array is :
[snip data]
time elapsed = 14.54592 ms

QuickSort()
sorted array is :
[snip data]
time elapsed = 0.61202 ms

original unsorted array (dimension=10000) :
[snip data]

Instantaneous sort + display results
sorted array is :
[snip data]
time elapsed = 2.51389 ms

PHP built-in array_sort() functions)
sorted array is :
[snip data]
time elapsed = 1.28102 ms

InsertionSort()
sorted array is :
[snip data]
time elapsed = 1163.08403 ms

QuickSort()
sorted array is :
[snip data]
time elapsed = 7.91597 ms

done.
This is the source code used in the iteration :
// generate demo data
//$original=array(1,1,2,3,4,4,5);
//$original=array(1,4,4,3,2,5,1); // to demonstrate sorting
// generate a $constMax-element array with random integer data spread between 1 and $constMax/10 (dense data)
$original=array();
for ($i=0;$i<$constMax;$i++) $original[$i]=rand(0,$constMax/10);

// display original data
echo "original unsorted array (dimension=".count($original).") : <BR>";
if ($constMax<=100) {
  for ($i=0;$i<count($original);$i++) echo "element $i : value ".$original[$i].'<BR>';
} else echo '[snip data]<BR>'; // else skip ;-)
echo "<BR>Instantaneous sort + display results<BR>";

TimerStart();
// ###################################################################
// ###########  1  tri instantané Vasiljevic #########################
// ###################################################################
// instantaneous sort
// initialisations
$result=array(); // considered initialized to zero values
$cMax=$constMax; // maximum expected limit for values' range
// "sort"
for ($i=0;$i<count($original);$i++) $result[$original[$i]]++;

// display results
echo "sorted array is :<BR>";
for ($i=0;$i<=$cMax;$i++) if ($result[$i]>0) for ($j=0;$j<$result[$i];$j++) if ($DISPLAYRES) echo "$i<BR>";
if (!$DISPLAYRES) echo '[snip data]<BR>';

$time1=TimerStop();

echo "time elapsed = $time1 ms <BR>";

echo "<BR>PHP built-in array_sort() functions)<BR>";

TimerStart();
// ###################################################################
// ###########  2  PHP sort() solution       #########################
// ###################################################################
$fruits=$original; // copy array (too bad sort() is void ;-)
sort ($fruits);
reset ($fruits);
// display results
echo "sorted array is :<BR>";
foreach($fruits as $key=>$val) if ($DISPLAYRES) echo "$val<BR>";
if (!$DISPLAYRES) echo '[snip data]<BR>';

$time2=TimerStop();

echo "time elapsed = $time2 ms <BR>";

echo "<BR>InsertionSort()<BR>";

//no more overflow on this new server
//if ($constMax>1000) $time2='****'; // overflow
//else {
  TimerStart();
  // ###################################################################
  // ###########  3  insertionSort solution    #########################
  // ###################################################################
  $result=insertionSort($original);
  // display results
  echo "sorted array is :<BR>";
  foreach($result as $key=>$val) if ($DISPLAYRES) echo "$val<BR>";
  if (!$DISPLAYRES) echo '[snip data]<BR>';


  $time2=TimerStop();
//} // overflow

echo "time elapsed = $time2 ms <BR>";


echo "<BR>QuickSort()<BR>";

TimerStart();
// ###################################################################
// ###########  3  QuickSort solution    #@@@@########################
// ###################################################################
$result=$original;
qsort($result, 0, count($result)-1); 
// display results
echo "sorted array is :<BR>";
foreach($result as $key=>$val) if ($DISPLAYRES) echo "$val<BR>";
if (!$DISPLAYRES) echo '[snip data]<BR>';

$time2=TimerStop();

echo "time elapsed = $time2 ms <BR>";

and those are the source code fragments present in this script :
// --------------------------------- Functions and Procedures --------------------------

function insertionSort($str_) {
   foreach ($str_ as $key => $val) {
     $val_[] = $val;
    $key_[] = $key;
   }
   for ($i = 1; $i < count ($val_); $i++) {
     $index = $val_[$i];
     $kindex = $key_[$i];
    $j = $i;
     while (($j > 0) && ($val_[$j - 1] > $index)) {
       $val_[$j] = $val_[$j - 1];
       $key_[$j] = $key_[$j - 1];
       $j = $j - 1;
     }
     $val_[$j] = $index;
     $key_[$j] = $kindex;
   }
   foreach ($val_ as $key => $val) {
     $new_[$key_[$key]] = $val;
   }
  return $new_;
 }

function swap(&$v, $i, $j) { 
  $temp = $v[$i]; 
  $v[$i] = $v[$j]; 
  $v[$j] = $temp; 
} 

// Quick Sort integer array - $int_array[$left] .. $int_array[$right] 
function qsort(&$int_array, $left, $right) { 
  if ($left >= $right) 
    return; // Do nothing if there are less than 2 array elements 
  swap ($int_array, $left, intval(($left+$right)/2)); 
  $last = $left; 
  for ($i = $left + 1; $i <= $right; $i++) 
    if ($int_array[$i] < $int_array[$left]) 
      swap($int_array, ++$last, $i); 
  swap($int_array, $left, $last); 
  qsort($int_array, $left, $last-1); 
  qsort($int_array, $last+1, $right); 
} 

9. Conclusion top

FR

En conclusion le tri instantané Vasiljevic (paru dans Théoric en 1983) est toujours aussi performant et bat tous les algorithmes classiques dont le QuickSort ; Le tri par insertion s'effondre au dela de 10000 éléments à trier ; les fonctions câblées dans PHP n'ont aucune concurrence possible (il faudrait câbler le tri instantané pour pouvoir comparer).
Les résultats étaient très différents à l'époque (le 07/04/2003) car le tri instantané battait les fonctions de base de PHP :

---------------------------------
original unsorted array (dimension=1000) : 
[snip data]

Instantaneous sort + display results
[snip data]
time elapsed = 24.05202 ms 

PHP built-in array_sort() functions)
[snip data]
time elapsed = 21.29793 ms 

InsertionSort()
[snip data]
time elapsed = 2122.159 ms 

QuickSort()
[snip data]
time elapsed = 163.47206 ms 

--------------------------------------------------------------------------------
original unsorted array (dimension=10000) : 
[snip data]

Instantaneous sort + display results
[snip data]
time elapsed = 481.19712 ms 

PHP built-in array_sort() functions)
[snip data]
time elapsed = 548.58303 ms 

InsertionSort()
time elapsed = **** ms 

QuickSort()
[snip data]
time elapsed = 2827.18503 ms 

--------------------------------------------------------------------------------
done.

J'ai aussi des versions plus complètes de cet algorithme de "tri instantané" : pour les chaînes de caractères, pour les nombres réels jusqu'à une précision donnée, etc et aussi des versions comparables à asort(), usort() etc (ie, "préservant les clefs" ou autrement dit "préservant un index pour retrouver les index des valeurs dans le tableau d'origine")

Cordialement,

EN

Conclusion : the instantaneous sort Vasiljevic (Théoric, 1983) is still as performant and beats all classical algorithms including QuickSort ; the Insertion Sort crashes beyond 10000 elements to sort ; built-in PHP functions are unbeatable in speed (we should hardcode the instantaneous sort to get a possibility of comparison).
As you may see immediately above, the original (2003-04-07) results were totally different in that the instantaneous sort beat the PHP built-in array functions...

Also, I've more complete versions of the instantaneous sort, for strings, floating-point numbers up to a given precision, etc and also some comparable to asort(), usort() etc (ie, "preserving keys" or otherwise "preserving some index to retrieve the indices of the values in the original array")

Best regards,

Vincent Graux (VGR) for European Experts Exchange and Edaìn Works  back to list of test scripts
Last update 2024-05-13 15:36:46