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