Quicksort recursive.php

From Algorithmist
Jump to navigation Jump to search

This is an implementation of Quicksort in PHP. This algorithm is recursive. Algorithm is a modified version available here [1].

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