quicksort.php

<?php
/* quicksort sorts an array by partitioning the array
 * into elements greater than a pivot point and elements
 * less than or equal to that pivot point.  the pivot point
 * is now in its final, sorted location by definition.
 * then, recursively perform the same operation on each half 
 * of the array.
 * efficiency: O(n log n)
 */
 
 
// performs quicksort on an array
function quicksort(&$arr, $lo, $hi) {
  
  // base case: lo is greater than or equal to hi
  if ($lo < $hi) {
    // find the index of the sorted item
    $partition_idx = partition($arr, $lo, $hi);
    
    // perform quicksort on the remaining portions
    quicksort($arr, $lo, $partition_idx-1);
    quicksort($arr, $partition_idx+1, $hi);
  }
}
// sorts an array at a partition point so that elements 
// < the partiton are on the left and elements >= are on the right
function partition(&$arr, $lo, $hi) {
  
  // set pivot to the last element in the array
  $pivot = $arr[$hi];
  
  // create an index store the pivot in its final location after the loop
  $i = $lo - 1;
  // iterate over array, swapping items less than or equal to the pivot
  for ($j = $lo; $j < $hi; $j++) {
    if ($arr[$j] <= $pivot) {
      
      // increment pivot plop point
      $i++;
      
      // place the located less than or equal item at a
      // location to the left of the future pivot location
      swap($arr, $i, $j);
    }
  }
  
  // swap the pivot to the point just after the loop left off
  swap($arr, $i+1, $hi);
  // return the index of the partition
  return $i + 1;
}
// swaps two elements in an array
function swap(&$arr, $i, $j) {
  $temp = $arr[$i];
  $arr[$i] = $arr[$j];
  $arr[$j] = $temp;
}
$arr = [33, 0, 1, -5, 1, 4, 2, -9, 1, 7, -1];
quickSort($arr, 0, count($arr)-1);
print_r($arr);
?>