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 ...
Get Core PHP Programming: Using PHP to Build Dynamic Web Sites now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
