Quick sort implementation in PHP

A simple quicksort creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, this will require O(n) extra storage space, which will impact the speed and efficiency particularly when the input is large. Here is an example of a simple quick sort implementation in PHP:

function simple_quick_sort($arr)
{
	if(count($arr) <= 1){
		return $arr;
	}
	else{
		$pivot = $arr[0];
		$left = array();
		$right = array();
		for($i = 1; $i < count($arr); $i++)
		{
			if($arr[$i] < $pivot){
				$left[] = $arr[$i];
			}
			else{
				$right[] = $arr[$i];
			}
		}
		return array_merge(simple_quick_sort($left), array($pivot), simple_quick_sort($right));
	}
}
$unsorted = array(5,3,8,6,2,7);
echo implode(",",$unsorted)." @unsorted<br>";
$sorted = simple_quick_sort($unsorted);
echo implode(",",$sorted)." @sorted<br>";

In-place quicksort sorts the array by swap array elements within the input array, thus it doesn’t require more storage allocation which in turn improves the efficiency. The trick here is to pass the array to be sorted in the partition function and quickSort function as a reference, so the sorting happens inside the function will directly affect the input array outside the function.

function partition(&$arr,$leftIndex,$rightIndex)
{
	$pivot=$arr[($leftIndex+$rightIndex)/2];
	
	while ($leftIndex <= $rightIndex) 
	{        
		while ($arr[$leftIndex] < $pivot)             
				$leftIndex++;
		while ($arr[$rightIndex] > $pivot)
				$rightIndex--;
		if ($leftIndex <= $rightIndex) {  
				$tmp = $arr[$leftIndex];
				$arr[$leftIndex] = $arr[$rightIndex];
				$arr[$rightIndex] = $tmp;
				$leftIndex++;
				$rightIndex--;
		}
	}
	echo implode(",",$arr)." @pivot $pivot<br>";
	return $leftIndex;
}

function quickSort(&$arr, $leftIndex, $rightIndex)
{
	$index = partition($arr,$leftIndex,$rightIndex);
	if ($leftIndex < $index - 1)
		quickSort($arr, $leftIndex, $index - 1);
	if ($index < $rightIndex)
		quickSort($arr, $index, $rightIndex);
}
$nums = array(5,3,8,6,2,7);
echo implode(",",$nums)." @unsorted<br>";
quickSort($nums,0,count($nums)-1);
echo implode(",",$nums)." @sorted<br>";

Output of the above in-place quick sort:

5,3,8,6,2,7 @unsorted
5,3,7,6,2,8 @pivot 8
5,3,2,6,7,8 @pivot 7
2,3,5,6,7,8 @pivot 3
2,3,5,6,7,8 @pivot 2
2,3,5,6,7,8 @pivot 5
2,3,5,6,7,8 @sorted

demo

Search within Codexpedia

Custom Search

Search the entire web

Custom Search