oster@lapis.berkeley.edu.UUCP (03/27/87)
There are a few "bugs" in the LightSpeed C libraries. They don't produce
the wrong answer, they are just funky C.
example: look at the code for quicksort.
1.) bad algorithm: it picks the first element of the array as the pivot
element. This means that is you qsort an array that is
a.) already sorted or
b.) sorted in reverse order
c.) almost sorted.
qsort will run in N*N time instead of N*Ln(N) time. If they'd picked the
middle element, it would have run in N*ln(N) time in the three common
cases listed above.
2.) bad C style. look at the comparison function (I quote from memory:) it
looks like:
int compar(a, b){
comparX(a, b);
}
and the value of compar is used by its caller. The correct code is:
int compar(a, b){
return comparX(a, b);
}
The only reason the LSC code works is because comparX leaves its value in
the function return register (rD0), and compar doesn't clobber it before
returning itself. Lint (if it existed for LightSpeed C) would have caught
this. Since this error was in the released code, we can infer that the
libraries weren't checked with lint and that the compiler probably wasn't
either. LightSpeed C is far and away the best compiler for the Macintosh.
A simple way for Think, Inc to increase the quality of their product is
just make it pass lint. (and while your at it, could you make it an
option? I'll buy it.)
I want to say thank you to all the folks at Think who have produced a
wonderful product. And a special thanks for sending us library source
code, so we can find and fix minor blemishes like these.
--- David Phillip Oster -- "We live in a Global Village."
Arpa: oster@lapis.berkeley.edu --
Uucp: ucbvax!ucblapis!oster -- "You are Number Six."