PHP Shaker Sort

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