Data Structure in PHP: Quicksort

Quicksort is one of the best method in sorting algorithm. It has best and average case performance as O(n Log n). It means for 100 element, sorting can take around 660 iterations whereas in bubble sort it will take around 10000 iteration. In the example below, which has eight elements, it can take 24 iteration. Quicksort's worst case performance is same as bubble sort which is O(n2). Last element in the list below is 0. Change that to 6 to see it goes to 26 iterations. So, element position in the list can affect its performance.

In the code below, you can find few lines that is not related to algorithm. Those are for checking how many iteration it takes to completes the sort. That is just for fun also. Echo related statement inside function is fun part I have added to see how it loops. You can delete that easily if that confuses you.


<?php
// Quicksort simple version
$l = 1;
function quicksort2($arr, $side) {
	if(!count($arr)) return $arr;
	global $l;
	static $l=1;
	$pivot = $arr[0];
	$less = $greater = array();
	// pivot is a pivot in a iteration. It is not included in less or greater. This will continue happen till base case of recursion lists
	$i = count($arr);
	while (--$i > 0) {
		echo "<p>$i ". count($arr) ." $side </p>";
		if($arr[$i] <= $pivot)
		{
			$less[] = $arr[$i];
		}
		else
		{
			$greater[] = $arr[$i];
		}
		 $l++;
	}
	echo "<p style='color:red'>$i ". count($arr) ." $side </p>";
	$GLOBALS['l'] = $l++;
	return array_merge(quicksort2($less, 'left'), array($pivot), quicksort2($greater, 'right'));
}
$arr = array(1,3,2,8,5,7,4,0);
echo '<pre>';
print("Before sorting");
print_r($arr);
$arr = quicksort2($arr, 'start');
print("After sorting by using Quick sort");
print_r($arr);
echo "Total: $l";
?>
Comments are open for an year period. Please, write here on Facebook page.