On 7/08/10 7:57 AM, bearophile wrote:
Peter Alexander:
Yeah, partition has always meant that to me as well.
Probably you come from a quite different part of computer science (The example
I have shown from Mathematica is not the only one).
What are the usages of that algorithm, beside being used in the QuickSort?
It's used a fair amount in geometry. I know the Kirkpatrick-Seidel
algorithm uses it and I've seen some Delaunay triangulation
implementations use it. I'm pretty sure there's other geometrical
applications for it as well.
Outside of specific algorithms, I think partition is quite a neglected
algorithm, because people typically just use sort, even when partition
would be more suitable. For example, consider some distribution service
that distributes some product to premium customers first, followed by
regular customers. Really, that's a job for partition, but in practice
your average Joe coder would just sort based on the same predicate,
wasting a factor of O(lg(n)). Either that or they'd just iterate over
the sequence twice: once for premium, and a second time for regular.
I think the main argument for calling it that is because it is called
that by almost all computer science literature. Do a Google search for
quick sort pseudocode. Almost invariably you'll find that they'll define
a helper function called partition, so programmers have come to learn
that that's what partition does.
(I just Googled for "quicksort pseudocode" and sure enough, all of the
top 10 entries that actually contained code defined a partition function
that does what std.algorithm.partition does).
