In some ways the quick sort uses a similar idea to the bubble sort in
that it compares items and swaps them if they are out of sequence. However,
the idea of the quick sort is to divide the list into smaller lists which
can then also be sorted using the quick sort algorithm. This is usually
done through recursion. Lists of length 0 are ignored and those of length
1 are considered to be sorted.

Quick sort, like Merge Sort, is a divide-and-conquer sorting algorithm.
The premise of quicksort is to separate the "big" elements from the "small"
elements repeatedly. The first step of the algorithm requires choosing a
"pivot" value that will be used to divide big and small numbers. Each
implementation of quicksort has its own method of choosing the pivot
value--some methods are much better than others. The implementation below
simply uses the first element of the list as the pivot value. Once the
pivot value has been selected, all values smaller than the pivot are placed
toward the beginning of the set and all the ones larger than the pivot are
placed to the right. This process essentially sets the pivot value in the
correct place each time. Each side of the pivot is then quicksorted.

Ideally, the pivot would be selected such that it were smaller than about half
the elements and larger than about half the elements. Consider the extreme
case where either the smallest or the largest value is chosen as the pivot:
when quicksort is called recursively on the values on either side of it,
one set of data will be empty while the other would be almost as large as
the original data set. To improve the efficiency of the sort, there are
clever ways to choose the pivot value such that it is extremely unlikely to
end up with an extreme value. One such method is to randomly select three
numbers from the set of data and set the middle one as the pivot. Though
the comparisons make the sort slightly slower, a "good" pivot value can
drastically improve the efficiency of quicksort.

- 1. Pick an element from the table you're sorting. We call this the
'pivot'.
- 2. Exchange the pivot with the right-most element in the table.
- 3. Go through the table from both left and right ends; from the left
end, search for elements GREATER than the pivot; from the right end, search for
elements SMALLER than the pivot.
- 4. When you find these two elements, exchange them and go on.
- 5. When the two go-throughs cross, exchange the pivot and the element
where the left go-through is pointing.
- 6. The pivot is on its final place in the table, and to the left
there's only elements smaller than it, to the right there's only elements
greater than it. Now perform the same process for both sides of the table
recursively.

Consider the data set 5 9 3 8 6 4 2 1 7 0. For simplicity, take the first
element as the pivot value, in this case the 5. After iterative comparisons,
the array has the following arrangement: [0 3 4 2 1 5 8 6 7 9]. Note that
all the values to the left of the 5 are smaller and all those to the right
are larger. When quicksort is called on the smaller half, the problem of a
"bad" pivot value is highlighted. Note that the array of smaller numbers,
[ 0 3 4 2 1 ] does not change and the next array that gets quicksorted is
practically the same: [ 3 4 2 1 ]. A complete trace of the algorithm
follows.

5 9 3 8 6 4 2 1 7 0

Quicksorting subarray: [ 5 9 3 8 6 4 2 1 7 0 ]

Quicksorting subarray: [ 0 3 4 2 1 ]

Quicksorting subarray: [ ]

Quicksorting subarray: [ 3 4 2 1 ]

Quicksorting subarray: [ 1 2 ]

Quicksorting subarray: [ ]

Quicksorting subarray: [ 2 ]

Quicksorting subarray: [ 4 ]

Quicksorting subarray: [ 8 6 7 9 ]

Quicksorting subarray: [ 7 6 ]

Quicksorting subarray: [ 6 ]

Quicksorting subarray: [ ]

Quicksorting subarray: [ 9 ]

0 1 2 3 4 5 6 7 8 9