The "clever" implementation of Quicksort uses two pointers, one coming in from the left, and the other coming in from the right. This website describes how the system works.
Thursday, 16 May 2013
Saturday, 19 January 2013
Tony Hoare's Classic Quicksort Algorithm Unleashed
Mergesort "without the Merge"
In 1960, Sri-Lankan-born and Oxford-Classics-educated (Merton College) Tony Hoare, while working at the Moscow State University, developed this radical new way of sorting arrays. Quicksort is a variation of mergesort, but without the merge. Memorising this method (amongst others) is much like memorising moves in chess, or card-counting in blackjack, in summary, it is surely simple, but requires an initial effort to absorb, in all its subtleties.
The Method
Consider the array a[1:n]. The first step is to pick an element p, that is between a[1] and a[2], let's say, arbitrarily that p = a[x]. Now you reorder the elements in the array, such that all elements before p are less than p, and all elements ahead of p are numerically greater than p. This step is the partitioning step. If you want to be fancy, you can call p the pivot element, but there is really no need for such fancy language. What matters is the methodology.
Now, this same partition algorithm can then be applied to both sides individually. In the end, no merge operation is needed as partitions are already in the correct order.
How good is it?
Quicksort makes on average n * log(n) comparisons to sort an array, although this can be n-squared in the worst case. Strictly speaking, using "big-oh" notation, quicksort is O(n-squared), since that is the upper bound for the sort.
It is widely recognised as the fastest sort algorithm, on average, based on comparison of keys.
A Candidate for Parallel Programming
Clearly, this repeated application of the partition function (a manifestation of the "divide and conquer" principle), makes quicksort an excellent candidate for parallel programming. There are, however, many variations of parallel quicksort and studying them can be quite confusing!
In 1960, Sri-Lankan-born and Oxford-Classics-educated (Merton College) Tony Hoare, while working at the Moscow State University, developed this radical new way of sorting arrays. Quicksort is a variation of mergesort, but without the merge. Memorising this method (amongst others) is much like memorising moves in chess, or card-counting in blackjack, in summary, it is surely simple, but requires an initial effort to absorb, in all its subtleties.
The Method
Consider the array a[1:n]. The first step is to pick an element p, that is between a[1] and a[2], let's say, arbitrarily that p = a[x]. Now you reorder the elements in the array, such that all elements before p are less than p, and all elements ahead of p are numerically greater than p. This step is the partitioning step. If you want to be fancy, you can call p the pivot element, but there is really no need for such fancy language. What matters is the methodology.
Now, this same partition algorithm can then be applied to both sides individually. In the end, no merge operation is needed as partitions are already in the correct order.
How good is it?
Quicksort makes on average n * log(n) comparisons to sort an array, although this can be n-squared in the worst case. Strictly speaking, using "big-oh" notation, quicksort is O(n-squared), since that is the upper bound for the sort.
It is widely recognised as the fastest sort algorithm, on average, based on comparison of keys.
A Candidate for Parallel Programming
Clearly, this repeated application of the partition function (a manifestation of the "divide and conquer" principle), makes quicksort an excellent candidate for parallel programming. There are, however, many variations of parallel quicksort and studying them can be quite confusing!
Subscribe to:
Comments (Atom)