Location: PHPKode > scripts > Brim::QuickSort > brim-quicksort/QuickSort.php
<?php

/**
 * QuickSort. This sorting algorithm uses a callback funtion (via a omparator,
 * so it can be implied to arrays, objects etc.
 * 
 * This file is part of the Brim project. The brim- project is located at the
 * following location: {@link http: //www.brim-project.org/ http://www.brim-project.org/}
 * 
 * <pre> Enjoy :-) </pre>
 *
 * @author Barry Nauta
 * @package org.brim-project.framework
 * @subpackage util
 *
 *
 * @copyright [brim-project.org] - Copyright (c) 2003 - 2005 Barry Nauta
 *
 * @license http://opensource.org/licenses/gpl-license.php 
 * The GNU Public License
 */
class QuickSort
{

	/**
	 * Default empty constructor
	 */
	function QuickSort ()
	{
		// nothing
	}
	
	/**
	 * The actual function
	 * @param array input object array containing objects to be sorted
	 * @param object comparator the comparator that compares two objects in 
	 * the input array
	 */
	function sort (&$input, $comparator)
	{
		$this->internalSort ($input, $comparator, 0, count($input));
	}
	
	/**
	 * The partial sorting function. Private/internal use only 
	 * @param array input object array containing objects to be sorted
	 * @param object comparator the comparator that compares two objects in 
	 * the input array
	 * @param int low the starting offset
	 * @param int high the ending offset
	 * @private
	 */
	function internalSort (&$input, $comparator, $low, $high)
	{
		if ($low < $high)
		{
			$tmpLow = $low;
			$tmpHigh = $high + 1;
			$current = $input[$low];
			
			$done = false;
			while (!$done)
			{
				
				while (++$tmpLow <= $high && 
					$comparator->compare ($input[$tmpLow], $current) < 0);
					
				while ($comparator->compare ($input[--$tmpHigh], $current) >0);
				
				if ($tmpLow < $tmpHigh)
				{
					$this->swap ($input, $tmpLow, $tmpHigh);
				}
				else
				{
					$done = true;
				}
			}
			$this->swap ($input, $low, $tmpHigh);
			$this->internalSort ($input, $comparator, $low, $tmpHigh-1);
			$this->internalSort ($input, $comparator, $tmpHigh+1, $high);
		}
	}
	
	/**
	 * Swap two elements in an array
	 * @param array input the input array
	 * @param int i the first element to be swapped
	 * @param int j the second element to be swapped
	 * @private
	 */
	function swap (&$input, $i, $j)
	{
		$temp = $input[$i];
		$input[$i]=$input[$j];
		$input[$j]=$temp;
	} 	
}
?>
Return current item: Brim::QuickSort