It's easy to see that the bubble sort is very inefficient, but if you ran the example in
Listing 15.1, you probably didn't get the impression it was slow. For tiny lists of fewer
than a hundred elements, the bubble sort is fine. If you have to code your own sort, the
bubble sort has the advantage of being easy to remember and simple enough to get right
the first time.
Quicksort
Invented by Professor C.A.R. Hoare in 1961, quicksort has proven to be the best general-
purpose sorting 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. In most implementations it relies on
recursion, a topic discussed in Chapter 4.
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 in Listing 15.2, 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.
Listing 15.2 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