4 Jun
2013
4 Jun
'13
7:05 p.m.
On 06/04/2013 02:04 PM, Fred Cisin wrote:
That's a great illustration of an extremely important concept, of adapting
the sort to the data and hardware configuration, and not being pushed to
look at a sort as some sort of sealed black box, based on assumptions of
"normal" hardware and "random" data.
I saw that particular fail most often with people who could not accept
that the "best" sort was NOT best when dealing with other situations,
particularly the situation where there already exists significant amount
of partial existing order.
I think I could still write a polyphase merge sort without consulting a
book. When you chart out how some external sorts operate, it's like
watching a a Rubik's cube solution. Pure poetry.
Knuth's book was excellent. I'd used a McGraw-Hill or Prentice-Hall
text before the Knuth text came out. I still have Knuth, but not the
other book, whose title I've long forgotten.
But there's also the idea of not gilding the lily with a too elaborate
sort. Case in point--I needed to print a sorted symbol table on a
compiler I was working on. This was a single-user system with on-line
(dot matrix) printer. I chose a selection sort because each pass
through the symbol table took less time than it did to print the
preceding line. The only storage required was a flag in the symbol
table (at that point, I was through with the names, so I just clobbered
the first character in each name as I printed it). The symbol table
always printed at full printer speed. The code was minuscule. We were
using floppies for storage, so even printing to disk was fast enough.
Sometimes the "stupid" algorithms are good enough.
-Chuck