A Visual Guide To Quicksort
The other writeups in this node do a strong job of describing the algorithm, but for many with interest or education in computer science, an example may help to illustrate the quicksort algorithm.
Problem: We have a list of sixteen names. We want to put these names in alphabetical order. Here is the list:
Adams
Edgar
Garrett
Knowles
Jones
Lawrence
Maxine
Hancock
Norbert
Fish
Oliver
Irene
Detroit
Cass
Philip
Brown
Solution: We will use the quicksort algorithm to sort this list.
The quicksort algorithm uses a divide and conquer approach to sorting a list. The algorithm separates a given list into two separate lists, then sorts each of these lists. This is done through the concept of a pivot point.
A pivot point is a single element from the list that is correctly placed in the position it should have in the final, ordered list. This is done by selecting an item from the list by some method (often, it is chosen randomly).
For the first pass, let's choose Hancock as the pivot point.
Adams
Edgar
Garrett
Knowles
Jones
Lawrence
Maxine
Hancock
Norbert
Fish
Oliver
Irene
Detroit
Cass
Philip
Brown
The next step sorting the remainder of the list into two distinct piles: less than the chosen item, and more than the chosen item. In essence, you're pivoting the list around the pivot point.
Adams
Edgar
Garrett
Fish
Detroit
Cass
Brown
Hancock
Knowles
Irene
Jones
Lawrence
Maxine
Norbert
Oliver
Philip
In the end, you have a pile of n items that should be ranked before the pivot item, followed by the item itself in the n + 1 position, and then a pile of m items that should be ranked after the pivot item. Obviously, the total number of items that you're sorting is n + m + 1. The stacks can be seen above in their rough order.
Recursion comes in at this point. On each unsorted pile of items, you merely call quicksort again. From each of the piles a pivot point is selected...
Adams
Edgar
Garrett
Fish
Detroit
Cass
Brown
Hancock
Knowles
Irene
Jones
Lawrence
Maxine
Norbert
Oliver
Philip
... and then each of these stacks with a new pivot point is sorted around the pivot point as before, with the lesser ones going before the point and the greater ones going after.
Adams
Cass
Brown
Detroit
Edgar
Fish
Garrett
Hancock
Knowles
Irene
Jones
Lawrence
Maxine
Norbert
Oliver
Philip
This concept is then repeated with each of the new small stacks:
Adams
Brown
Cass
Detroit
Edgar
Fish
Garrett
Hancock
Irene
Jones
Knowles
Lawrence
Maxine
Norbert
Oliver
Philip
When the piles are of size 1, as almost all of the ones shown above, that means the item is already at its correct place in the list, thus no need to execute quicksort.
Typically, on a very small array (of size 20 or less), other sorts are chosen because they are faster on very small sets, but in terms of large sets, it usually far surpasses other sorts.
Hopefully, this should make some of the computer science-heavy writeups in this node more clear in terms of how the algorithm works.