# Quick Sort Function

By jayon crow
on March 22, 2007

Version: 2.1

Type: Function

Category: Algorithms

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

```
﻿