sorting algorithms

[Kurt Luoto]

In article <1989Nov17.185514.15726 at algor2.algorists.com> jeffrey at algor2.ALGORISTS.COM (Jeffrey Kegler) writes:
>In article <6916 at ficc.uu.net> peter at ficc.uu.net (Peter da Silva) writes:
>>I like Horowitz and Sahni, "Fundamentals of Computer Algorithms". They're
>>a lot more readable than Knuth, and use a high-level pseudocode for
>>everything. (whatever posessed Knuth to express algorithms in assembly?)
>
>It is important to remember that Knuth's sorting book is over 15 years
>old in a field that moves very quickly.  In particular, the decision
>to use assembly, while by current standards, very ill-advised, looked
>better then.  C use was not then widespead (the UNIX kernel had just
>been rewritten in C from assembler), so what was Knuth to do?  Use
>FORTRAN?  ALGOL?  Either probably would have been better, actually,
>than MIX, but at least you can see that Knuth's choice was a rational
>one at the time.

I won't pretend to be expert enough to speak for Knuth, but there are
some reasons for using a (pseudo-)assembly language.  (I might have read
these from an interview with Knuth, but don't take my word for it.)
Mr. Kegler points out one good reason.  Another reason is that it is good
for students of computing to have a feel for what goes on inside of a
computer, even if they are going to be programming in a high-level language.
It is much easier to explain the costs of various algorithms when you
have a concrete model to compare with.  With the MIX model, you can "run"
your algorithm, count execution cycles or storage requirements, 
and actually *see* the costs/behaviour for various cases.  In a high
level language it is somewhat harder to get a feel for these things.
For example, not all statements in C or Pascal have the same cost,
These may not be compelling reasons, but they are rational.

>The "standard" answer to algorithms questions is "read Knuth" (a
>variant of RTFM), but I feel this is more of a dismissal than an
>answer.  Knuth is far more often cited or used as a status symbol then
>read.  You need not have been around this business as long as I have
>to have seen Knuth's volumes behind the desks of many a poor excuse
>for a programmer.  Knuth is still an important source, but is no
>longer up to date and was always hard to read.  I often wonder if his
>problems do more to scare readers off than increase their
>understanding of the field.

It is true that some will find Knuth's style somewhat inaccessible.
First, I think this is because he is a mathematician by training and is
targeting a math-literate audience.  In fact, a large chunk of his first
volume seems devoted to simply providing the mathematical tools necessary
for the later volumes, where much of the material of interest to programmers
is found.

Second, it seems to me that he is writing more for theorists,
those whose field is the mathematics of computation (I *hate* the term
"computer science"!) as opposed to writing a reference for programmers
who "just want the algorithms" (cookbook procedures) without the theoretical
derivations.  Its sort of like a calculus text written for math majors,
which includes all the proofs, as opposed to a calculus text written for
engineers or soft-sciences which gives the statement of the theorems
and the formulas, but leaves out the proofs.

Third, Knuth crams *a lot* of material into his volumes.  If you have
worked through all of his exercises (I have not), you have learned much indeed.
But for practical every-day use, you usually only need a fraction of the
information.  Other texts will lead you more quickly to this fraction.

>
>Knuth should not be anyone's first book on algorithms.  Learning
>algorithms from Knuth is almost as bad as learning physics from Newton
>in the Latin original.

I agree that there are better introductory texts.  But if you have the
time and motivation, I cannot see how learning from Knuth can in any
way be "bad".  We could use more programmers with good mathematical training.

>-- 
>
>Jeffrey Kegler, Independent UNIX Consultant, Algorists, Inc.
>jeffrey at algor2.ALGORISTS.COM or uunet!algor2!jeffrey
>1762 Wainwright DR, Reston VA 22090
-- 

----------------
Kurt W. Luoto     kurtl at fai.com   or   ...!sun!fai!kurtl