<?php

/**
 * QuickSort performs an enhanced quicksort on an array of comparable data.
 * Comparable data is typically integers, floats, doubles, or strings which 
 * should compare as integer values. The enhancement mentioned is the use of
 * an Insertion sort algorithm when a predefined cutoff limit has been reached.
 * The cutoff improves the speed of QuickSort when it reaches small unsorted arrays.
 * The qsort algorithm used is modified from Wikipedia's C implementation of QuickSort.
 * See this implementation here: http://en.wikipedia.org/wiki/Quicksort
 *
 * @copyright BSD license - You may change, use, distribute freely, but you cannot sell this class.
 */
class QuickSort{

	/**
	 * QuickSort constructor.
	 * @param $array - An unsorted array of comparable data.
	 */
	function QuickSort($array){
		$this->unsorted = $array;
	}
	
	/**
	 * This is a standard setter for recycling this class.
	 * You can set the array to another array and resort and get the
	 * newly sorted array again.
	 * @param $array - An unsorted array of comparable data.
	 */
	function setArray($array){
		$this->unsorted = $array;
	}
	
	/**
	 * sortArray sorts the array which was loaded in the constructor. A cutoff of 1500
	 * is used to switch the quicksort algorithm to a insertion sort algorithm. 1500 was
	 * determined to be the optimal number for any input size. If the input is smaller than 1500
	 * items then only insertion sort will be used.
	 */
	function sortArray(){
		$this->sorted = $this->qsort( $this->unsorted,0,count($this->unsorted),1500 );
	}
	
	/**
	 * getSortedArray returns the sorted array after the sortArray
	 * function has been called. It will return NULL if the sortArray function
	 * has not been called.
	 * @return The sorted array
	 */
	function getSortedArray(){
		return $this->sorted;
	}
	
	/**
	 * doSortAndGetSortedArray is the lazy-man's function
	 * for performing the sort on the pre-loaded array 
	 * (load the array in the constructor) and returning the 
	 * sorted array. To use this function just load the array in the 
	 * constructor and call this method. The sorted array is returned.
	 * @return The sorted array.
	 */
	function doSortAndGetSortedArray(){
		$this->sortArray();
		return $this->getSortedArray();
	}
	
	/**
	 * @private
	 * qsort is a private function which performs all of the sorting work.
	 * It takes an array which is passed by reference and recursively breaks
	 * the array into smaller and smaller sub parts. It sorts the sub parts
	 * around a pivot point and breaks those sub parts by the pivot and recursively 
	 * calling qsort again. A cutOff is used to limit the qsort algorithm, because 
	 * qsort doesn't work very well with small input an insertion sort algorithm is used.
	 * @param $array - An array of comparable data (ints, floats, doubles, or strings compared by int value).
	 * @param $lowPos - A position to start sorting at. First sort call usually starts at 0.
	 * @param $highPos - A position to end sorting at. First sort call usually ends at count($array).
	 * @param $cutOff - A cutoff point to switch to Insertion sort. 1500 is a good position.
	 */
	function qsort(&$array, $lowPos, $highPos, $cutOff){
		if($lowPos + $cutOff > $highPos){
			$this->insertionSort($array,$lowPos,$highPos);
		}else{
			$left = $lowPos;
			$right = $highPos;
			$pivot = $array[$left];
			while ($left < $right){
				while (($array[$right] >= $pivot) && ($left < $right))
					$right--;
				if ($left != $right){
					$array[$left] = $array[$right];
					$left++;
				}
				while (($array[$left] <= $pivot) && ($left < $right))
					$left++;
				if ($left != $right){
					$array[$right] = $array[$left];
					$right--;
				}
			}
			$array[$left] = $pivot;
			$pivot = $left;
			if ($lowPos < $pivot)
				$this->qsort($array, $lowPos, $pivot, $cutOff);
			if ($highPos > $pivot)
				$this->qsort($array, $pivot+1, $highPos, $cutOff);
		}
		return $array;
	}
	
	/**
	 * insertionSort algorithm developed by Allan Bogh.
	 * This algorithm was developed specifically by Allan Bogh from scratch.
	 * It is a simple pull-out-and-insert-into-position algorithm, but it 
	 * may not exactly follow the true Insertion Sort method.
	 * @param $array - An array of numbers, passed by reference
	 * @param $low - A key specifying the starting point.
	 * @param $high - A key specifying the ending point.
	 * @return The sorted array, not used in pass by reference situations.
	 */
	function insertionSort(&$array, $low, $high){
		$i = $low+1;

		while ($i < $high) {
			//insert(a, i, a[i]);
			$j = $i - 1;
			$value = $array[$i];
			while ($j >= $low && $array[$j] > $value) {
				$array[($j + 1)] = $array[$j];
				$j--;
			}
			$array[$j + 1] = $value;
			$i++;
		}
		 
		return $array; //don't really need this in a pass by reference situation
	}
}

?>