I was reading a computational geometry textbook the
other day. And, in the first chapter, the author made
an offhand comment. Something along the lines of
"This is the standard way we build algorithms in
computational geometry. First we sort the input
data, then we construct the solution incrementally."
And a few moments ago, I was thinking about state
space search (for games) and I realized that much
the same thing is true. One sorts, builds, sorts,
builds, ....
Which suggests to me that there's a general
approach to algorithms here: When you're not sure
what to do, sort the data and deal with it piecemeal.
The big question: Is this a generally applicable
pattern? Or is it only for certain restricted
domains like, say, AI and Computational Geometry?
Is sorting a more powerful tool than I had hitherto
realized? What other algorithmic patterns use
sorting?
--
WilliamGrosso
Is
sorting taken
to mean
separating
as opposed to
ordering?
--
WardCunningham
I'm a little confused as to how to read the above with sorting meaning separating but not especially ordering. However, in computer graphics real time simulators, we used to organize the polygons in special ways to simplify their processing. This would count as separating the data into groups, and then working on the groups separately. We also ordered the groups, and within groups when we could. --
AlistairCockburn
Don't
sorting and
separating fall
under the more general banner of
organizing?
The general approach to many problems is to first organize data
(e.g., sort it, separate it into piles, structure it for quick retrieval
or efficient querying),
and then to analyze or process the aggregate.
SortAndBuild might be the trivial case of
DivideAndConquer.
--
DaveSmith
I meant "ordering" by sorting. And this may be just as
trivial as
DaveSmith says, but it still struck me
as interesting.
When you're designing objects, you can use a laundry
list of questions in order to guide the process,
suggest object structures, and make sure you haven't
overlooked anything that commonly occurs.
What I'm starting to sense is that there is a similar
list of questions and, possibly, patterns at a much
lower level (I knew that patterns scaled up, but
didn't really suspect they scaled down. My natural
stupidity shining forth, I guess).
WilliamGrosso