range chunks

[Peter Alexander]

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).