11 Apr
2006
11 Apr
'06
5:58 p.m.
On 4/11/2006 at 8:13 PM William Donzelli wrote:
If I have a nice fast microcontroller, and I need to do
a sort of a
bunch of numbers, in many cases I can make a brain dead choice and use
something like a bubble sort and get away with it. If my engineering
manager knew I spent a whole day trying to find a perfect sort, yet the
end result makes no difference to the rest of the project - well, my raise
my not be too hot that year.
Wonder why everyone mentions "bubble sort" when they mean a relatively
inefficient sort? A selection sort is actually much slower ( for n
elements, you make n-1 passes comparing n elements). But maybe not--on
some SIMD systems with high startup overhead per instruction, the selection
sort can be the fastest, for n less than some suprisingly large number, say
1000.
On the other hand, if the sort represents a small enough part of the entire
job, it may not matter what's used. I wrote a compiler that used a
selection sort for the symbol cross-reference. Typically, the program was
driving a printer and number of symbols was fairly small (less than
100)--optimizing would have taken more memory and not contributed a single
second to reducing the elapsed time to get a listing.
The engineering part IMOHO is knowing what and how much of something to
use.
Cheers,
Chuck