Site hosted by 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):

57 23 14 6 First of all, a pivot element is selected
37251 46 It is swapped with the first element in the partition (to get it out of the way!).
37251 46 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
31257 46 Whenever it finds any two such elements, it swaps them.
31257 46 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!
21357 46 ...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.
21357 46 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).
12357 46 And, lastly, we sort the larger partition...
12345 67