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

// 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>";

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>";

// --------------------------------- 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

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.

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,

for European Experts Exchange and Edaìn Works  back to list of test scripts
Last update 2010-01-18 08:50:34

Add This Article To:
Del.icio.us	Digg	Google	Spurl
Blink	Furl	Simpy	Y! MyWeb