6 Apr
2009
6 Apr
'09
9:13 p.m.
On 6 Apr 2009 at 13:40, Fred Cisin wrote:
I've run into "CS" graduates from the
university who supposedly have
learned about really "good" sort algorithms (usually
"Shell-Metzner"),
without understanding which situations an optimized "bubble" is better
for.
Heh. When I worked on a compiler that produced on-line listings, the
issue of printing the cross-reference list came up. Space was tight
(this was a 64KB systerm) and disks (floppy) were slow. It turned
out that a simple selection sort was more than adequate to keep the
printer busy.
Internal sorts were a gotcha on the STAR too. SInce *all*
instructions were essentially vector (with scalar being treated as a
vector of length 1), startup overhead for short vectors and scalars
was hideous. For arrays of less than about 1000 words, a simple
selection sort was faster than any of the "super-duper" algorithms,
as one could use a single vector select instruction.
--Chuck