Tuesday, April 12, 2011

Heap sort in php

Heapsort is a member of selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.
 
<?php
    function build_heap(&$array, $i, $t){
  $tmp_var = $array[$i];    
  $j = $i * 2 + 1;
  
  while ($j <= $t)  {
   if($j < $t)
    if($array[$j] < $array[$j + 1]) {
     $j = $j + 1; 
    }
   if($tmp_var < $array[$j]) {
    $array[$i] = $array[$j];
    $i = $j;
    $j = 2 * $i + 1;
   } else {
    $j = $t + 1;
   }
  }
  $array[$i] = $tmp_var;
 }

 function heap_sort(&$array) {
  //This will heapify the array
  $init = (int)floor((count($array) - 1) / 2);
  // Thanks jimHuang for bug report
  for($i=$init; $i >= 0; $i--){
   $count = count($array) - 1;
   build_heap($array, $i, $count);
  }
  
  //swaping of nodes
  for ($i = (count($array) - 1); $i >= 1; $i--)  {
   $tmp_var = $array[0];
   $array [0] = $array [$i];
   $array [$i] = $tmp_var;
   build_heap($array, 0, $i - 1);
  }
 }

// Demo
$array = array(9,8,7,6,5,4,3,2,1,0,10,1000,0);
heap_sort($array);
print_r($array);
?>

2 comments:

  1. There is a bug:

    $init = (count($array) - 1) / 2;

    Should be:

    $init = (int)floor((count($array) - 1) / 2);

    ReplyDelete