Advertisement
Guest User

PHP benchmark with heap sort

a guest
Dec 19th, 2013
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 1.12 KB | None | 0 0
  1. <?php
  2.  
  3. define('N', 10000000);
  4.  
  5. $h = array_fill(0, N, 0);
  6.  
  7. main();
  8.  
  9. function down($pos, $n) {
  10.     global $h;
  11.     while (true) {
  12.         $j = 2 * $pos + 1;
  13.         if ($j >= $n) {
  14.             break;
  15.         }
  16.         if ($j + 1 < $n && $h[$j + 1] > $h[$j]) {
  17.             $j++;
  18.         }
  19.         $t = $h[$pos];
  20.         if ($t >= $h[$j]) {
  21.             break;
  22.         }
  23.         $h[$pos] = $h[$j];
  24.         $h[$j] = $t;
  25.         $pos = $j;
  26.     }
  27. }
  28.  
  29. function main() {
  30.     global $h;
  31.    
  32.     $start = round(microtime(true) * 1000);
  33.    
  34.     for ($i = 0; $i < N; $i++) {
  35.         $h[$i] = $i;
  36.     }
  37.    
  38.     for ($i = (int) (N / 2); $i >= 0; $i--) {
  39.         down($i, N);
  40.     }
  41.    
  42.     $n = N;
  43.    
  44.     while ($n > 1) {
  45.         $n--;
  46.         $t = $h[0];
  47.         $h[0] = $h[$n];
  48.         $h[$n] = $t;
  49.         down(0, $n);
  50.     }
  51.    
  52.     foreach ($h as $i => $v) {
  53.         if ($i !== $v) {
  54.             echo "Sorting failed at index $i!\n";
  55.             return;
  56.         }
  57.     }
  58.    
  59.     $finish = round(microtime(true) * 1000);
  60.     $delta = $finish - $start;
  61.    
  62.     echo "Done in $delta ms!\n";
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement