Iskren Stoyanov's blog

B-tree - Add element/node

2007-11-30T19:50:00.000-08:00

Here follows an example of creating "Multiway B-Tree".

The implementation is in PHP:




// B-tree
function btree_search( $value, $a, &$higher, $v)
{
 global $tree, $q, $u, $n, $nn;
 
 static $v;
 
 // create new elelemt
 if( $tree[$a]['m'] == 0 )
 {
  $higher = true;
  $v['value'] = $value;
  $v['count'] = 1;
  $v['p'] = null;
  
  $u = $v;
 }
 else
 {
   $cur = $tree[$a];
   $l = 1;
   $r = $cur['m'];

   do// binary search
   {
    $k = (int)( ($l + $r)/2);
    if( $value <= $cur['el'][$k]['value'] )
    {
     $r = $k - 1;
    }
    if( $value >= $cur['el'][$k]['value'] )
    {
     $l = $k + 1;
    }
   }while( $r >= $l);

   // found
   if( $l - $r > 1)
   {
    $cur['el'][$k]['count']++;
    $higher = false;
   }
   else
   {
    if( $r == 0 )
     $q = $cur['p0'];
    else
     $q = $cur['el'][$r]['p'];
    
    btree_search($value, $q, $higher, $u);
    if( $higher )
    {
     /* $a !== null. Search key $value in B-tree with root $a;
       insert new item with key $value. If an entry is to be passed up,
       assign it to $v. $higher = "tree has become higher"
    */
     
     $cur = &$tree[$a];
    
     // !$higher
    if( $cur['m'] < $n*2 )
    {
     $cur['m']++;
     $higher = false;

     
     for( $i=$cur['m']; $i >= $r+2; $i-- )
     {
      $cur['el'][$i] = $cur['el'][$i-1];
      
     }
     
     $cur['el'][$r+1] = $u;
     
    }
    // page $tree[$a]/$cur is full.
    // It's partioned and the odd element is moved to v 
    else
    {
     // add new element to $tree and assign
     // the last element's num to $b;
     $b = array_push($tree, array());
     if( $r <= $n ) // insert in left page $a
     {
      if( $r == $n )
       $v = $u;
      else
      {
       $v = $cur['el'][$n];
       for( $i=$n; $i >= $r+2; $i-- )
        $cur['el'][$i] = $cur['el'][$i-1];
       
       $cur['el'][$r+1] = $u;
      }
      for( $i=1; $i <= $n; $i++ ){
       $tree[$b]['el'][$i] = $cur['el'][$i+$n];
       unset( $cur['el'][$i+$n] );
      }
     }
     else // insert into right page $b
     {
      $r = $r-$n;
      $v = $cur['el'][$n+1];
      for( $i=1; $i <= $r-1; $i++ )
       $tree[$b]['el'][$i] = $cur['el'][$i+$n+1];
      $tree[$b]['el'][$r] = $u;
       
      for( $i=$r+1; $i <= $n; $i++ )
       $tree[$b]['el'][$i] = $cur['el'][$i+$n];
      
     }
     $cur['m'] = $n;
     $tree[$b]['m'] = $n;
     $tree[$b]['p0'] = $v['p'];
     $v['p'] = $b;
     
     $u = $v;
    }
    }
   }
 }
 return 1;
}

$b_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$b_tree;
// array for B-tree insert test
// test steps bellow to see how the tree behaves 
$values = array(20);
//$values = array(20, 40, 10, 30,15);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25 );

$higher = false;
$root = null;
$n = 2;
foreach( $values as $val )
{

 btree_search( $val, $root, $higher, $u);
 if( $higher )
 {
  $q = $root;
  if( count($tree) == 0 )
  {
   $tree = array(1=>array());
   $root = 1;
  }
  else
   $root = array_push($tree, array());

  $tree[$root]['m'] = 1;
  $tree[$root]['p0'] = $q;
  
  $tree[$root]['el'][1] = $u;
 }
}

B-tree - Remove element/node

2007-11-30T19:49:00.000-08:00

Here follows an example of deleting from "Multiway B-Tree".

PHP code:



function btree_delete($value, $a, &$higher)
{
 /*  search and delete key $value in B-tree a; if a page underflow arises,
  balance with adjacent page or merge; $higher := "page $a is undersize" */
 
 global $tree, $n;
 
 if( $a === null )
 {
  $higher = false;
 }
 else
 {
  $l = 1;
  $r = $tree[$a]['m'];
  
  // binary search
  do
  {
   $k = (int)( ($l + $r)/2 );
   if( $value <= $tree[$a]['el'][$k]['value'] )
    $r = $k -1;
   if( $value >= $tree[$a]['el'][$k]['value'] )
    $l = $k +1;
  }while( $r >= $l );
  
  
  if( $r === 0 )
  {
   $q = $tree[$a]['p0']; // go to the left
  }
  else
   $q = $tree[$a]['el'][$r]['p']; // go to the right
   
  if( $l - $r > 1)
  {
   // $a is leaf page
   if( $q === null )
   {
    $tree[$a]['m']--;
    $higher = ($tree[$a]['m'] < $n )? true: false;
    
    for( $i=$k; $i <= $tree[$a]['m']; $i++ )
    {
     $tree[$a]['el'][$i] = $tree[$a]['el'][$i+1];
    }
   }
   else
   {
    btree_del($q,$a, $higher, $k);
    if( $higher )
    {
     underflow( $a , $q, $r, $higher, $k); 
    }
   }
  }
  else
  {
   btree_delete( $value, $q, $higher );
   if( $higher )
   {
    underflow( $a, $q, $r, $higher, $k );
   }
  }
 }
 
}

function underflow( $c, $a, $s, &$higher, &$k )
{
 /* $a = underflowing page, $c = ancestor page,
  $s = index of deleted entry in c */
 
 global $tree, $n;
 
 $mc = $tree[$c]['m'];
 
 if( $s < $mc ) 
 {
  $s++;
  
  // $b = page to the right of a
  $b = $tree[$c]['el'][$s]['p'];
  $mb = $tree[$b]['m'];
  
  // $k = nof items available on page b
  $k = (int)( ($mb - $n+1)/2 );
  
  $tree[$a]['el'][$n] = $tree[$c]['el'][$s];
  
  $tree[$a]['el'][$n]['p'] = $tree[$b]['p0'];

  if( $k > 0 )// balance by moving k-1 items from $b to $a
  {
   for( $i=1; $i <= $k-1; $i++ )
   {
    $tree[$a]['el'][$i+$n] = $tree[$b]['el'][$i];
   }
   $tree[$c]['el'][$s] = $tree[$b]['el'][$k];
   $tree[$c]['el'][$s]['p'] = $b;
   
   $tree[$b]['p0'] = $tree[$b]['el'][$k]['p'];
   $mb -= $k;/////// +1
   
   for( $i=1; $i <= $mb; $i++  )
   {
    $tree[$b]['el'][$i] = $tree[$b]['el'][$i+$k];
   }
   $tree[$b]['m'] = $mb;
   $tree[$a]['m'] = $n-1 +$k;
   $higher = false;

  }
  else// merging a and b, discard b
  {
   for( $i=1; $i <= $n; $i++ )
   {
    $tree[$a]['el'][$i+$n] = $tree[$b]['el'][$i];
   }
   for( $i=$s; $i <= $mc-1; $i++)
   {
    $tree[$c]['el'][$i] = $tree[$c]['el'][$i+1];
   }
   $tree[$a]['m'] = 2*$n;
   $tree[$c]['m'] = $mc - 1;
  }
 }
 else
 {
  // $b = page to the left of $a
  if( $s == 1 )
  {
   $b = $tree[$c]['p0'];
  }
  else
  {
   $b = $tree[$c]['el'][$s-1]['p'];
  }
  $mb = $tree[$b]['m']+1;
  $k = (int)( ($mb - $n)/2 );
  
  if( $k > 0 )
  {
   for( $i=$n-1; $i >= 1; $i-- )
   {
    $tree[$a]['el'][$i+$k] = $tree[$a]['el'][$i]; 
   }
   $tree[$a]['el'][$k] = $tree[$c]['el'][$s];
   $tree[$a]['el'][$k]['p'] = $tree[$a]['p0'];

   // move k-1 items from $b to $a, one to $c

   $mb -= $k;//////// +1
   
   for( $i=$k-1; $i >= 1; $i-- )
   {
    $tree[$a]['el'][$i] = $tree[$b]['el'][$i+$mb]; 
   }
   $tree[$a]['p0'] = $tree[$b]['el'][$mb]['p'];
   
   $tree[$c]['el'][$s] = $tree[$b]['el'][$mb];
   $tree[$c]['el'][$s]['p'] = $a;
   
   $tree[$b]['m'] = $mb -1;
   $tree[$a]['m'] = $n-1 +$k;

   $higher = false;
   
  }
  else //merge pages $a and $b, discard $a
  {
   $tree[$b]['el'][$mb] = $tree[$c]['el'][$s];
   $tree[$b]['el'][$mb]['p'] = $tree[$a]['p0'];
   
   for( $i=1; $i <= $n-1; $i++ )
   {
    $tree[$b]['el'][$i+$mb] = $tree[$a]['el'][$i];
   }
   $tree[$b]['m'] = 2*$n;
   $tree[$c]['m'] = $mc - 1;
  }
 }
}

function btree_del($p, $a, &$higher, &$k)
{
 global $tree, $n;
 
 $m = &$tree[$p]['m'];
 
 $q = $tree[$p]['el'][$m]['p'];
 if( $q !== null )
 {
  btree_del($q, $a, $higher, $k);
  if( $higher )
   underflow($p, $q, $m, $higher, $k);
 }
 else
 {
  $tree[$p]['el'][$m]['p'] = $tree[$a]['el'][$k]['p'];
  $tree[$a]['el'][$k] = $tree[$p]['el'][$m];
  
  $m--;

  $higher = ($m < $n )? true: false;
 }
}

Full example of creating and delete from B-Tree here

Balanced tree - Add element/node

2007-11-26T15:58:00.000-08:00

This script add element to the tree if it doesn't exist, if exists just increment it counter.



function search_btree( $value, $ptr, $higher, $ptr0 = 0,$node = 'left' )
{
 global $tree;
 static 
  $first_run = 1,
  $higher,
  $beginning;  
 
 if( !$tree[$ptr]['value'] )// insertion
 {
  if( !$first_run )// create new element in the tree array - $tree
  {
   $tree[] = array();
   $ptr = count($tree)-1;
    
   $tree[$ptr0][$node] = $ptr;// put current node in parent's left or right node

  }else{// $tree[0] is already create so we just use is
   $first_run--;
   $beginning = $ptr;
  }
  $higher = true;
  
  $tree[$ptr]['value'] = $value;
  $tree[$ptr]['left'] = null;
  $tree[$ptr]['right'] = null;
  $tree[$ptr]['bal'] = 0;
  $tree[$ptr]['count'] = 1;
  
 }
 else
 {
  if( $value < $tree[$ptr]['value'] )
  {
   search_btree( $value, $tree[$ptr]['left'], $higher, $ptr );
   if( $higher )
   {
    switch( $tree[$ptr]['bal'] )
    {
     case 1:
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
     case 0:
      $tree[$ptr]['bal'] = -1;
     break;
     case -1:
      $ptr1 = $tree[$ptr]['left'];
      if( $tree[$ptr1]['bal'] == -1) // individualli flip LL
      {
       
       $tree[$ptr]['left'] = $tree[$ptr1]['right'];
       $tree[$ptr1]['right'] = $ptr;
       $tree[$ptr]['bal'] = 0;


       if( $ptr == $beginning )
        $beginning = $ptr1;
       // replaces $ptr with $ptr1 in parent left or right node
       replace_pointer_link( $ptr, $ptr1 );
       $ptr = $ptr1;
      }
      else
      {
       $ptr2 = $tree[$ptr1]['right'];

       $tree[$ptr1]['right'] = $tree[$ptr2]['left'];
       $tree[$ptr2]['left'] = $ptr1;
       
       $tree[$ptr]['left'] = $tree[$ptr2]['right'];
       $tree[$ptr2]['right'] = $ptr;
       
       if( $tree[$ptr2]['bal'] == -1 )
        $tree[$ptr]['bal'] = 1;
       else
        $tree[$ptr]['bal'] = 0;
        
       if( $tree[$ptr2]['bal'] == 1 )
        $tree[$ptr1]['bal'] = -1;
       else
        $tree[$ptr1]['bal'] = 0;
       
       if( $ptr == $beginning )
        $beginning = $ptr2;
       replace_pointer_link( $ptr, $ptr2 );
       $ptr = $ptr2;
       
      }
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
    }
   }
  }
  else if( $value > $tree[$ptr]['value'] )
  {
   search_btree( $value, $tree[$ptr]['right'], $higher, $ptr, 'right' );
   if( $higher )
   {
    switch( $tree[$ptr]['bal'] )
    {
     case -1:
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
     case 0:
      $tree[$ptr]['bal'] = 1;
     break;
     case 1:
      $ptr1 = $tree[$ptr]['right'];
      if( $tree[$ptr1]['bal'] == 1 )// individualli flip RR
      {

       $tree[$ptr]['right'] = $tree[$ptr1]['left'];
       $tree[$ptr1]['left'] = $ptr;
       
       $tree[$ptr]['bal'] = 0;
       
       if( $ptr == $beginning )
        $beginning = $ptr1;
       replace_pointer_link( $ptr, $ptr1 );
       $ptr = $ptr1;
      }
      else//RL
      {
       
       $ptr2 = $tree[$ptr1]['left'];
       
       $tree[$ptr1]['left'] = $tree[$ptr2]['right'];
       $tree[$ptr2]['right'] = $ptr1;
       
       $tree[$ptr]['right'] = $tree[$ptr2]['left'];
       $tree[$ptr2]['left'] = $ptr;
       
       if( $tree[$ptr2]['bal'] == 1 )
        $tree[$ptr]['bal'] = -1;
       else
        $tree[$ptr]['bal'] = 0;
       
       if( $tree[$ptr2]['bal'] == -1 )
        $tree[$ptr1]['bal'] = 1;
       else
        $tree[$ptr1]['bal'] = 0;
       
       if( $ptr == $beginning )
        $beginning = $ptr2;

       replace_pointer_link( $ptr, $ptr2 );
       $ptr = $ptr2;
      }
      $tree[$ptr]['bal'] = 0;
      $higher = false;
     break;
    }
   }
  }
  else
  {
   $tree[$ptr]['count']++;
   $higher = false;
  }
 }
 return $beginning;
}
//replaces $old_ptr with $new_ptr in the parent node's left or right node
function replace_pointer_link( $old_ptr, $new_ptr )
{
 global $tree;

 for( $i=0; $i < count($tree); $i++)
 {
  if( $i === $new_ptr )
   continue;//prevents replacing $old_ptr with $new_ptr in $tree[$new_ptr] 
 
  // if $tree[$i]['left'] is empty and we are checking for link to node 0($old_ptr=0),
  // ('' == 0)==true, but ('' === 0)==false
  // we don't need to put link to node 0 on empty nodes
  if( $tree[$i]['left'] === $old_ptr ){
   $tree[$i]['left'] = $new_ptr;
   return;
   }
   elseif( $tree[$i]['right'] === $old_ptr)
  {
   $tree[$i]['right'] = $new_ptr;
   return;
  }
 }

}
//
// Example:
//

$my_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$my_tree;
$start = 0;

// test all 4 cases of rebalancing when
// adding element in balanced tree
$values = array( 4, 5, 7, 2, 1, 3, 6);
foreach( $values as $val )
{
 $start = search_btree( $val, $start, false);
}
echo "<html><body>";
echo "start=$start;";
echo "<pre>";
print_r( $my_tree );
echo "</pre>";
echo "<br><br>";
echo "</body></html>";

?>

Source

Balanced tree - Remove element/node

2007-11-26T15:55:00.000-08:00

Delete element from balanced tree:



//replaces $old_ptr with $new_ptr in the parent node's left or right node
function replace_pointer_link( $old_ptr, $new_ptr )
{
 global $tree;

 for( $i=0; $i < count($tree); $i++)
 {
  if( $i === $new_ptr )
   continue;//prevents replacing $old_ptr with $new_ptr in $tree[$new_ptr] 
 
  // if $tree[$i]['left'] is empty and we are checking for link to node 0($old_ptr=0),
  // ('' == 0)==true, but ('' === 0)==false
  // we don't need to put link to node 0 on empty nodes
  if( $tree[$i]['left'] === $old_ptr ){
   $tree[$i]['left'] = $new_ptr;
   return;
   }
   elseif( $tree[$i]['right'] === $old_ptr)
  {
   $tree[$i]['right'] = $new_ptr;
   return;
  }
 }

}
function delete( $value, $ptr, $higher)
{
 global $tree, $q, $start;
 static $higher;
 
 if( !$tree[$ptr]['value'] )
 {
  echo "KEY IS NOT IN TREE";
  $higher = false;
 }
 elseif( $value < $tree[$ptr]['value'] )
 {
  delete( $value, $tree[$ptr]['left'], $higher );
  if( $higher )
   balance1( $ptr, $higher);
 }
 elseif ( $value > $tree[$ptr]['value'] )
 {
 delete( $value, $tree[$ptr]['right'], $higher );
  if( $higher )
   balance2( $ptr, $higher);
 }
 else
 {
  $q = $ptr;
  if( $tree[$q]['right'] === null )
  {
   replace_pointer_link( $ptr, $tree[$q]['left'] );
   unset($tree[$q]);
   $higher = true; 
  }
  elseif( $tree[$q]['left'] === null )
  {
   replace_pointer_link( $ptr, $tree[$q]['right']);
   unset($tree[$q]);
   $higher = true;
  }
  else
  {
   del( $tree[$q]['left'], $higher );
   if( $higher )
    balance1( $ptr, $higher);
  
  }
 }
 
}
function balance1( $ptr, &$higher)
{
 global $tree, $start;
 switch( $tree[$ptr]['bal'] ){
  case -1: 
   $tree[$ptr]['bal'] = 0;// after del tree is balanced
  break;
  case 0://after deletion tree is higher in the right side
   $tree[$ptr]['bal'] = 1;
   $higher = false;
  break;
  case 1: // tree must be rebalanced
   $ptr1 = $tree[$ptr]['right'];
   $bal1 = $tree[$ptr1]['bal'];
   
   if( $bal1 >= 0 )// single flip RR
   {
    $tree[$ptr]['right'] = $tree[$ptr1]['left'];
    $tree[$ptr1]['left'] = $ptr;
    
    if( $bal1 == 0 )
    {
     $tree[$ptr]['bal'] = 1;
     $tree[$ptr1]['bal'] = -1;
     $higher = false;
    }else{
     $tree[$ptr]['bal'] = 0;
     $tree[$ptr1]['bal'] = 0;
    }
    
    // start pointer is replaced we need to change $start
    if( $ptr == $start )
     $start = $ptr1;
    replace_pointer_link($ptr, $ptr1);
   }
   else // double flip RL
   {
    $ptr2 = $tree[$ptr1]['left'];
    $bal2 = $tree[$ptr2]['bal'];
    
    $tree[$ptr1]['left'] = $tree[$ptr2]['right'];
    $tree[$ptr2]['right'] = $ptr1;
    
    $tree[$ptr]['right'] = $tree[$ptr2]['left'];
    $tree[$ptr2]['left'] = $ptr;
    
    if( $bal2 == 1 )
    {
     $tree[$ptr]['bal'] = -1;
    }else{
     $tree[$ptr]['bal'] = 0;
    }
    if( $bal2 == -1 )
    {
     $tree[$ptr1]['bal'] = 1;
    }else{
     $tree[$ptr1]['bal'] = 0;
    }

    if( $ptr == $start )
     $start = $ptr2;
    replace_pointer_link( $ptr, $ptr2);
    $tree[$ptr2]['bal'] = 0;
   }
   
  break;
 }
}

function balance2( $ptr, &$higher )
{
 global $tree, $start;
 switch( $tree[$ptr]['bal'] )
 {
  case 1:
   $tree[$ptr]['bal'] = 0;
  break;
  case 0:
   $tree[$ptr]['bal'] =-1;
   $higher = false;
  break;
  case -1:
   $ptr1 = $tree[$ptr]['left'];
   $bal1 = $tree[$ptr1]['bal'];
   
   if( $bal1 <= 0 )// single flip LL
   {
    $tree[$ptr]['left'] = $tree[$ptr1]['right'];
    $tree[$ptr1]['right'] = $ptr;
    
    if( $bal1 == 0 )
    {
     $tree[$ptr]['bal'] = -1;
     $tree[$ptr1]['bal'] = 1;
     $higher = false;
    }
    else
    {
     $tree[$ptr]['bal'] = 0;
     $tree[$ptr1]['bal'] = 0;
    }
    if( $ptr == $start )
     $start = $ptr1;
    replace_pointer_link( $ptr, $ptr1);
   }
   else// double flip LR 
   {
    $ptr2 = $tree[$ptr1]['right'];
    $bal2 = $tree[$ptr2]['bal'];
    
    $tree[$ptr1]['right'] = $tree[$ptr2]['left'];
    $tree[$ptr2]['left'] = $ptr1;
    
    $tree[$ptr]['left'] = $tree[$ptr2]['right'];
    $tree[$ptr2]['right'] = $ptr;
    
    if( $bal2 == -1 )
     $tree[$ptr]['bal'] = 1;
    else
     $tree[$ptr]['bal'] = 0;
    if( $bal2 == 1 )
     $tree[$ptr1]['bal'] = -1;
    else
     $tree[$ptr1]['bal'] = 0;
    
    if( $ptr == $start )
     $start = $ptr2;
    replace_pointer_link($ptr, $ptr2);
    $tree[$ptr2]['bal'] = 0;
   }
  
 }
}
function del( $ptr, &$higher )
{
 global $tree, $q;
 if( $tree[$ptr]['right'] )
 {
  del( $tree[$ptr]['right'], $higher);
  if( $higher )
   balance2( $ptr, $higher);
 }
 else
 {
  $tree[$q]['value'] = $tree[$ptr]['value'];
  $tree[$q]['count'] = $tree[$ptr]['count'];
  
  replace_pointer_link($ptr, $tree[$ptr]['left']);
  if( $ptr == $start )
   $start = $tree[$ptr]['left'];

  unset($tree[$ptr]);
  $higher = true;
 }
}
$my_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$my_tree;
$start = 0;

// array for testing deletion in balanced tree 
$values = array(5, 3, 8, 2, 4, 7, 10, 1, 6, 9, 11);

foreach( $values as $val )
{
 $start = search_btree( $val, $start, false);
}
echo "<html><body>";
echo "start=$start;";
echo "<pre>";
print_r( $my_tree );

delete( 4, $start, false);
delete( 8, $start, false);
delete( 6, $start, false);
delete( 5, $start, false);
delete( 2, $start, false);
delete( 1, $start, false);
delete( 7, $start, false);


echo "start=$start<br>";
print_r($tree);

echo "</pre>";
echo "<br><br>";
echo "</body></html>";

Source

Generate perfectly balanced tree

2007-11-26T15:45:00.000-08:00

The script that follows generates perfectly balanced tree with "n" nodes:


function tree( $num_nodes )
{
 global $tree;
 
 if( $num_nodes == 0 )
  return null;
 
 $left = (int)($num_nodes / 2);
 $right = $num_nodes - $left -1;
 
 $tree[]['value'] = (int)(rand( 1, 50) / $num_nodes+1);
 $last = count($tree)-1;
 
 $tree[$last]['left'] = tree( $left );
 $tree[$last]['right'] = tree( $right );
 
 return $last;
}

Eight queens

2007-11-14T00:32:00.000-08:00

Here is recursive algorithm solving the problem with eight queens which don't threaten each other:



function check( $i )
{
 global $column, $rows, $left_d, $right_d;
 for( $j = 1; $j <= 8; $j++ )
 {
  // check is the row and both diagonals are free
  if( $rows[$j] && $left_d[$i+$j] && $right_d[$i-$j] )
  {
   $column[$i] = $j;//put the qeen on the $i column in the $j position
   
   //set row and diagonals to occupied 
   $rows[$j] = false;
   $left_d[$i+$j] = false;
   $right_d[$i-$j] = false;
   
   // if $i == last column(8) we print the results
   if( $i < 8 )
    check( $i + 1 );
   else
    print_results();
   
   //unset row and diagonals
   $rows[$j] = true;
   $left_d[$i+$j] = true;
   $right_d[$i-$j] = true;
  }
 }
}

function print_results()
{
 global $column;
 foreach( $column as $value )
  echo $value ."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
 
 echo "<br />\n";
}

for( $i = 1; $i <= 8; $i++ )
 $rows[$i] = true;

for( $i = 2; $i <= 16; $i++ )
 $left_d[$i] = true;
  

for( $i = -7; $i <= 7; $i++ )
 $right_d[$i] = true;

check(1);

Benchmark

2007-11-09T13:52:00.000-08:00

Here is benchmark of all array sorting algorithms post in the blog. Sorting arrays of 10 000 elements:

Name	random	sorted	rsorted
straightInsertion	7.48131	0.0095	13.68925
binaryInsertion	5.46446	0.05528	10.8473
straightSelection	21.2452	21.34226	25.2773
bubbleSort	22.76245	12.45991	31.98982
shakerSort	18.75352	0.00392	32.69624
heapSort	0.11843	0.12559	0.11432
quickSortRecursive	11.91182	6.7423	6.43074
quickSortRecursiveNew	7.41534	7.45058	7.38413
quickSort	0.05555	0.02845	0.03096
sort	0.00869	0.00467	0.005

Different sort algorithms have advantage in certain conditions. So this benchmark can't show the advantage of all of them.

Function quickSortRecursive receives an array as parameter and then creates new static array for the recursion calls. quickSortRecursiveNew uses global array and it sorts random array faster then quickSortRecursive.
The iterative version of quick sort is more then 100 faster then recursive one!!!

The last function is PHP native function for sorting arrays. It so fast because it isn't run through PHP interpreter. Use PHP native functions, they are a lot faster.

The source of benchmark and all of the functions can be found here.

Quicksort

2007-11-09T13:32:00.000-08:00

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.

Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

PHP implementation:



// Recursive version:
function quickSortRecursive( $arr, $left = 0 , $right = NULL )
{
 // when the call is recursive we need to change 
 //the array passed to the function yearlier
 static $array = array(); 
 if( $right == NULL )
  $array = $arr;

 if( $right == NULL )
  $right = count($array)-1;//last element of the array
 
 $i = $left;
 $j = $right;
 
 $tmp = $array[(int)( ($left+$right)/2 )];

 // partion the array in two parts. 
 // left from $tmp are with smaller values,
 // right from $tmp are with bigger ones
 do
 {
  while( $array[$i] < $tmp )
   $i++;
  
  while( $tmp < $array[$j] ) 
   $j--;
  
  // swap elements from the two sides 
  if( $i <= $j )
  {
   $w = $array[$i];
   $array[$i] = $array[$j];
   $array[$j] = $w;
   
   $i++;
   $j--;
  }
 }while( $i <= $j );
 
 // devide left side if it is longer the 1 element
 if( $left < $j )
  quickSortRecursive(NULL, $left, $j);
 
 // the same with the right side
 if( $i < $right )
  quickSortRecursive(NULL, $i, $right);

 // when all partitions have one element
 // the array is sorted
 
 return $array;
}




// Non recursive version:
function quickSort( $array )
{
 $cur = 1;
 $stack[1]['l'] = 0;
 $stack[1]['r'] = count($array)-1;
 
 do 
 {
  $l = $stack[$cur]['l'];
  $r = $stack[$cur]['r'];
  $cur--;
  
  do
  {
   $i = $l;
   $j = $r;
   $tmp = $array[(int)( ($l+$r)/2 )];

   // partion the array in two parts.
   // left from $tmp are with smaller values,
   // right from $tmp are with bigger ones
   do
   {
    while( $array[$i] < $tmp )
     $i++;
    
    while( $tmp < $array[$j] ) 
     $j--;
    
    // swap elements from the two sides 
    if( $i <= $j )
    {
     $w = $array[$i];
     $array[$i] = $array[$j];
     $array[$j] = $w;
     
     $i++;
     $j--;
    }
   
   }while( $i <= $j );
   

   if( $i < $r )
   {
    $cur++;
    $stack[$cur]['l'] = $i;
    $stack[$cur]['r'] = $r;
   }
   $r = $j;
  
  }while( $l < $r );
  
 }while( $cur != 0 );

 return $array;
}

Heapsort

2007-11-09T13:27:00.000-08:00

Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.

During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)

Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.

PHP implementation:



function heapSort( $array )
{
 $right = count( $array )-1;
 $left = (int)($right/2) + 1;
 
 while( $left > 0 )
 {
  $left--;
  sift($array, $left, $right);
 }
 
 while( $right > 0 )
 {
  $tmp = $array[0];
  $array[0] = $array[$right];
  $array[$right] = $tmp;
  $right--;
  
  sift($array, $left, $right);
 }
 
 return $array;
}
function sift( &$array, $left, $right )
{
 $i = $left;
 $j = 2*$i;
 $tmp = $array[$i];
 
 while( $j <= $right )
 {
  if( $j < $right && $array[$j] < $array[$j+1] )
   $j++;
  if( $tmp >= $array[$j] ){
   $array[$i] = $tmp;
   return 0;
  }
  $array[$i] = $array[$j];
  $i = $j;
  $j = 2*$i;
 }
 
 $array[$i] = $tmp;
}

Shaker Sort

2007-11-09T13:24:00.001-08:00

Shaker sort is a simple optimization that does passes in both directions, allowing out of place items to move fast across the whole array. Same complexity as Bubble sort, only works much better when some smal items are at the end of the array.

PHP implementation:



function shakerSort( $array )
{

 $l = 1;
 $r = count($array)-1;
 $k = $r;
 
 do
 {
  //move smaller values to the left
  for( $j=$r; $j >= $l; $j-- )
   if( $array[$j-1] > $array[$j] )
   {
    $tmp = $array[$j-1];
    $array[$j-1] = $array[$j];
    $array[$j] = $tmp;
    $k = $j;
   }
  $l = $k+1;
  // move bigger values to the right
  for( $j=$l; $j <= $r; $j++ ){
   if( $array[$j-1] > $array[$j])
   {
    $tmp = $array[$j-1];
    $array[$j-1] = $array[$j];
    $array[$j] = $tmp;
    $k = $j;
   }
  }
  $r = $k-1;
 }while( $l <= $r );

 return $array;
}

Bubble sort

2007-11-09T13:16:00.000-08:00

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.

example: 5 1 4 2 8 - unsorted array 1 4 2 5 8 - after one pass 1 2 4 5 8 - sorted array

The algorithm gets its name from the way smaller elements "bubble" to the top (i.e. the beginning) of the list via the swaps. (Another opinion: it gets its name from the way greater elements "bubble" to the end.) Because it only uses comparisons to operate on elements, it is a comparison sort. This is the easiest comparison sort to implement.

PHP implementation:



function bubbleSort( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
  // move smaller from two elements up until reach current position
  for( $j = (count($array)-1); $j >= $i; $j-- )
   if( $array[$j-1] > $array[$j] )
   {
    $tmp = $array[$j-1];
    $array[$j-1] = $array[$j];
    $array[$j] = $tmp;
   }

 return $array;
}

Selection sort

2007-11-09T13:08:00.000-08:00

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has Θ(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations. It works as follows:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)

Effectively, we divide the list into two parts: the sublist of items already sorted, which we build up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.

PHP implementation:



function straightSelection( $array )
{

 for( $i=0; $i < count($array); $i ++ )
 {
  $k = $i;
  $tmp = $array[$i];
  
  // search elements right to current for the smallest
  for( $j = $i+1; $j < count($array); $j++ )
   if( $array[$j] < $tmp )
   {
    $k=$j;
    $tmp = $array[$j];
   }
  
  // switch places of current element and previously found
  $array[$k] = $array[$i];
  $array[$i] = $tmp;
 }

 return $array;
}

Binary Insertion sort

2007-11-09T13:00:00.000-08:00

The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires Θ(n) comparisons in the worst case, a binary search only requires Θ(logn) comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.

PHP implementation:


function binaryInsertion( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
 {
  $tmp = $array[$i];
  $left = 0;
  $right = $i-1;
  
  // finds the last element with value smaller then current element
  // all elements before the current are sorted
  // so we can find the middle and
  // check only the right(correct) half
  while( $left <= $right )
  {
   $middle = (int)(($left+$right)/2);
   if( $tmp < $array[$middle] )
    $right = $middle - 1;
   else
    $left = $middle + 1;
  }
  // loop until current element is smaller than previous.
  // if so replace current with previous.
  for( $j = $i-1; $j >= $left; $j-- )
   $array[$j+1] = $array[$j];
  
  $array[$left] = $tmp;
  // now we can write current element's value on its position.
 }

 return $array;
}

Straight Insertion sort

2007-11-09T12:55:00.000-08:00

The key step of any insertion sorting algorithm involves the insertion of an item into a sorted sequence. There are two aspects to an insertion--finding the correct position in the sequence at which to insert the new element and moving all the elements over to make room for the new one.

This section presents the straight insertion sorting algorithm. Straight insertion sorting uses a linear search to locate the position at which the next element is to be inserted.

PHP implementation:


function straightInsertion( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
 {
  $tmp = $array[$i];
  // store current element's value because it
  // will be overwritten if it is not in its place
  
  // loop until current element is smaller than previous.
  // if so replace current with previous.
  for( $j = $i-1; $tmp < $array[$j]; $j-- )
   $array[$j+1] = $array[$j];

  // now we can write current element's value on its position.
  $array[$j+1] = $tmp;
 }

 return $array;
}