- pick one element in the array, which will be the
*pivot*. - make one pass through the array, called a
*partition*step, re-arranging the entries so that:- the pivot is in its proper place.
- entries smaller than the pivot are to the left of the pivot.
- entries larger than the pivot are to its right.

- recursively apply quicksort to the part of the array that is to the left of the pivot, and to the part on its right.

The algorithm starts with an array of random numbers. Each number is represented with a vertical stick. The height of the stick indicates the value of the number, and its left-right position indicates its location in the array. Click on "Run" to start the demo.

Now let's see what happens if the numbers in the array are already sorted. As we can see, quicksort does a lot of work for nothing! The problem here comes from the way the pivot is chosen. In this implementation, the pivot is always the last element in the array. More careful versions of quicksort pick a pivot that is more likely to belong near the middle of the array.

Quicksort is most effective on large arrays of random numbers.
In the following demo, we use the *Dots* view, where each
number is represented with a dot.
The partitioning step shows up here, as the data is repeatedly
grouped into two rectangles. The left rectangle appears because
numbers the left of the pivot are smaller than the pivot,
and hence their dots are all below the pivot's position.
Similarly, the right rectangle shows how numbers larger than the pivot
end up to the right of it.

Alejo Hausner, CS Department, Princeton University Last modified: Tue Jul 23 14:30:47 1996