<?php
//=====================================================================================================
// sortIt: sort an array using recursive processing 
//     args: array to be sorted
//
//For each pass, this sort will place the first element exactly where it is suppose to be in the array.
//In doing so, it will also move all the elements that are less than the first element to the top,
//and will move all the elements that are greater than the first element to the bottom.
//The sort will split the array at the position where the first element is supposed to be. 
//The sort will recursively call the sort for the top section, and again for the bottom section.  
//=====================================================================================================

print "<h2>Sorting Recursively - Quick Sort</h2>";

global $inArray;
global $num;

$inArray = range(0, 9);
shuffle($inArray);
//$inArray = array(5,6,8,1,3,7,0,9,2,4);

$num = 0;

print "<b>Starting random order: </b> ";
print (implode(', ', $inArray));                  //flatten array into a string, and print      
print "<br><br>";

sortIt($inArray);

print "<br>";
print "<b>Final order: </b> ";
print (implode(', ', $inArray));                  //flatten array into a string, and print      
print "<br><br>";

print "Number of iterations: " . $num;

//---------------------------------------------------------------------------------------------
function sortIt($inArray)                         //receives an array to be sorted 
{
    global $inArray;  

    print "<b>Sort . . . . . : </b> ";
    print (implode(', ', $inArray));              //flatten array into a string, and print      
    print "<br>";
    sortQuick($inArray,0,count($inArray)-1);      //call sortQuick on the full array
}

//---------------------------------------------------------------------------------------------
function sortQuick($inArray,$from,$to)            //receives an array and starting & ending position 
{
    global $inArray, $num;  

    if ($from >= $to) return;                       //end the recursion

    $num++;                                         //iteration number

    $top = $from;
    $bot = $to;
    $direction = -1;                                //start direction going up

    while ($top < $bot)
    {
        if ($inArray[$top] > $inArray[$bot])
        {
                $temp          = $inArray[$top];    //switch elements
                $inArray[$top] = $inArray[$bot];
                $inArray[$bot] = $temp;
                $direction    *= -1;                //flip direction                                                            
        }       
        ($direction == 1)? $top++ : $bot--;         //if direction down then top++, else bottom--
    }

    print ". . . . . Iteration <b>$num</b> Placing num <b>$inArray[$top] : </b> ";
    print (implode(', ', $inArray));                //flatten array into a string, and print      
    print "<br>";
    
    sortQuick($inArray, $from, $top-1);           //call recursion for the top half
    sortQuick($inArray, $bot+1,$to);              //call recursion for the bottom half    
}    
    
//====================================================================================================
?>

<?php include "../include.php"; ?>              <!-- hyperlink to see the code -->