Site hosted by Angelfire.com: Build your free website today!

How Quicksort works

The basic idea of Quicksort is to repeatedly divide the array into smaller pieces (these are called partitions), and to recursively sort those partititons. Quicksort divides the current partition by choosing an element - the pivot - finding which of the other elements are smaller or larger, sorting them into two different sub-partitions (one for the values smaller than the pivot, one for those larger than the pivot). For example, say we have the input (5,7,2,3,1,4,6). Here's what happens in the first partitioning run of a standard Quicksort algorithm (one that always chooses the middle element of the current partition as the pivot):

Data							Comments
5	7	2	3	1	4	6	First of all, a pivot element is selected
3	7	2	5	1	4	6	It is swapped with the first element in the partition (to get it out of the way!).
3	7	2	5	1	4	6	The program searches from the left for an element that belongs to the right of the pivot element, and from the right for an element that belongs to the left
3	1	2	5	7	4	6	Whenever it finds any two such elements, it swaps them.
3	1	2	5	7	4	6	Eventually the search from the left and the search from the right reach the same place. If, at the place where the search stops, the element belongs on the left of the pivot element, it is swapped with it. That's not the case here!
2	1	3	5	7	4	6	...Otherwise, the pivot element is swapped with the element to the left of the spot where the search stopped. Quicksort implementations that skip this step may not terminate.
2	1	3	5	7	4	6	We recursively call the Quicksort algorithm to sort the smaller of the two subpartitions (in this case, there are two elements on the left of the pivot, and four on the right, so we sort the left and then the right).
1	2	3	5	7	4	6	And, lastly, we sort the larger partition...
1	2	3	4	5	6	7