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