Quick Sort Iterative

Quick sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

									function Swap(&$a, &$b)
{
	$temp = $a;
	$a = $b;
	$b = $temp;
}

function Partition(&$data, $left, $right)
{
	$x = $data[$right];
	$i = ($left - 1);

	for ($j = $left; $j <= $right - 1; $j++)
	{
		if ($data[$j] <= $x)
		{
			$i++;
			Swap($data[$i], $data[$j]);
		}
	}

	Swap($data[$i + 1], $data[$right]);

	return ($i + 1);
}

function QuickSortIterative(&$data, $count) {
	$startIndex = 0;
	$endIndex = $count - 1;
	$top = -1;

	$stack = array();
	$stack[$top++] = $startIndex;
	$stack[$top++] = $endIndex;

	while ($top >= 0)
	{
		$top--;
		$endIndex = $stack[$top];
		$top--;
		$startIndex = $stack[$top];

		$p = Partition($data, $startIndex, $endIndex);

		if ($p - 1 > $startIndex)
		{
			$stack[$top++] = $startIndex;
			$stack[$top++] = $p - 1;
		}

		if ($p + 1 < $endIndex)
		{
			$stack[$top++] = $p + 1;
			$stack[$top++] = $endIndex;
		}
	}

	$stack = null;
}

Example

									$data = array(-1, 25, -58964, 8547, -119, 0, 78596);
QuickSortIterative($data, 7);

Output