Quicksort PHP

Invented by Professor C.A.R. Hoare in 1961, quicksort has proven to be the best generalpurposesorting algorithm. Many computer languages offer a library version, and PHP uses it for its built-in sorting functions. It is based on the same idea of exchanging elements, but adds the concept of partitioning.

The quicksort algorithm chooses a pivot element and then divides all elements by whether they are greater or lesser than the pivot. Each subsection is further divided similarly. When the granularity becomes small enough, elements are simply compared and possibly swapped, as in the bubble sort.

When we first call the quicksort function, we pass the first and last elements of the array as the left and right limits. This will cause the entire array to be sorted. The step taken inside the function is to pick a pivot. Considering performance, the median of all the numbers would be best. This would divide the array exactly in two. To find the median, however, takes work. Rather than add this overhead, I've chosen to simply pick the number in the middle.

Quicksort

<?
/*
** Quicksort
** input_array is an array of integers
** left is the leftmost element to be considered
** right is the rightmost element to be considered
*/
function Quicksort(&$input_array, $left_limit,
$right_limit)
{
//start pointers
$left = $left_limit;
$right = $right_limit;
//Choose the middle element for the pivot
$pivot_point = intval(($left + $right)/2);
$pivot = $input_array[$pivot_point];
do
{
while(($input_array[$left] < $pivot) AND
($left <
$right_limit))
{
$left++;
}
while(($pivot < $input_array[$right]) AND
($right >
$left_limit))
{
$right—;
}
if($left <= $right)
{
//swap elements
$temp = $input_array[$left];
$input_array[$left] =
$input_array[$right];
$input_array[$right] = $temp;
$left++;
$right—;
}
}
while($left <= $right);
if($left_limit < $right)
{
Quicksort(&$input_array, $left_limit,
$right);
}
if($left < $right_limit)
{
Quicksort(&$input_array, $left,
$right_limit);
}
}
$data = array(6, 13, 99, 2, 33, 19, 84);
//print array
print("<H3>Unsorted</H3> ");
print("<PRE>");
print_r($data);
print("</PRE> ");
//sort array
Quicksort(&$data, 0, count($data)-1);
//print array again
print("<H3>Sorted</H3> ");
print("<PRE>");
print_r($data);
print("</PRE> ");
?>

The next step is to divide the list into two halves. Starting from the outside, elements are checked for being greater than or less than the pivot. When two elements are found that are both on the wrong side, they are swapped. When the left and right pointers meet, each side is fed back to the quicksort function.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

PHP Topics