Snippets Algorithms
Algorithms
Quick Sort Function
by: jayon crow
|
March 22, 2007
Version: 2.1
Type: Function
Category: Algorithms
License: GNU General Public License
Description: a quick sort function Very useful!
/* Author: JBLamer, Date: 20070322
*
* qsort is a recursive quicksort function of an array
*
* $array_to_sort is the array that needs sorting
* the keys are pulled and replaced with a normal numeric array
* false is returned if $array_to_sort is not an array
* and true is returned otherwise
*
* $btm and $top are internal to track positions in the array
* $lvl in internal to track depth, leave at zero
*
* this uses the swap() function which takes two elements and swaps them
*/
function qsort( &$array_to_sort, $btm=null, $top=null, $lvl=0 )
{
// check if top of recursion and do checks
// otherwise the checks slow down the recursion
if ( $lvl == 0 )
{
if ( !is_array($array_to_sort) )
{ return false; }
// yank all the values out to prevent incorrect keying
$array_to_sort = array_values($array_to_sort);
$btm=0;
$top=count($array_to_sort)-1;
}
$lo = $btm;
$hi = $top;
$pivot = $array_to_sort[$hi];
// throw highs and lows to each side of the element
// and the one element will be in the correct position,
// then array is already partially sorted
while ( $lo < $hi )
{
while ( $lo < $hi && $pivot > strval($array_to_sort[$lo]) )
{ $lo++; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }
while ( $lo < $hi && strval($array_to_sort[$hi]) > $pivot )
{ $hi--; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }
}
// now $lo and $hi are on the sorted element
if ( $lo-1 > $btm ) // if equal, there is only one sorted element
{ qsort($array_to_sort, $btm, $lo-1, $lvl+1); }
if ( $top > $lo+1 ) // see last comment
{ qsort($array_to_sort, $lo+1, $top, $lvl+1); }
return true;
}
/* Author: JBLamer, Date: 20070322
*
* qsort0 is a nonrecursive quicksort function of an array
*
* $array_to_sort is the array that needs sorting
* the keys are pulled and replaced with a normal numeric array
* false is returned if $array_to_sort is not an array
* and true is returned otherwise
*
* This is handy on machines that have memory management issues
* that the recursive function can trigger on huge arrays.
* Actually on many speed tests, this was the quicker
* but that may be because of all the checks on recursion...
*
* this uses the swap() function which takes two elements and swaps them
*/
function qsort0( &$array_to_sort )
{
if ( !is_array($array_to_sort) )
{ return false; }
// yank all the values out to prevent incorrect keying
$array_to_sort = array_values($array_to_sort);
// record where we are via stack
$track_sort = array();
array_push($track_sort, array(0, count($array_to_sort)-1));
while ( count($track_sort) > 0 )
{
$hold = array_pop($track_sort);
$lo = $hold[0];
$hi = $hold[1];
$pivot = $array_to_sort[$hi];
// throw highs and lows to each side of the element
// and the one element will be in the correct position,
// then array is already partially sorted
while ( $lo < $hi )
{
while ( $lo < $hi && $pivot > strval($array_to_sort[$lo]) )
{ $lo++; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }
while ( $lo < $hi && strval($array_to_sort[$hi]) > $pivot )
{ $hi--; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }
}
// now $lo and $hi are on the sorted element
if ( $lo-1 > $hold[0] ) // if equal, there is only one sorted element
{ array_push($track_sort, array($hold[0], $lo-1)); }
if ( $hold[1] > $lo+1 ) // see last comment
{ array_push($track_sort, array($lo+1, $hold[1])); }
}
return true;
}
// this function is to swap element a with b
if ( !function_exists('swap') )
{
function swap( &$a, &$b )
{
$h = $a;
$a = $b;
$b = $h;
}
}
PHPBuilder
Policies
PHP Developer
Topics
PHP Developer
Resources
PHP Developer
References
