Re: Low-level vs. High-level programming (was My First Computer)

[russotto@grace.speakeasy.net (Matthew Russotto)]

In article <20030620140705.08084.00000744@mb-m16.aol.com>,
Michael J. Mahon <mjmahon@aol.com> wrote:
>Matthew Russotto replied:
>
>>You could probably rig things to make bubble sort useful -- make it so
>>data movement cost is proportional to the distance of the movement.
>>
>>>(BTW, for very small numbers of items, the "repeatedly pick lowest
>>>and set it to infinity" algorithm ("pick and zot") is usually the fastest,
>>>although it is exactly n**2.)
>>
>>I believe that's the selection sort by another name.
>
>Hmmm.  I thought you said it was n log n...

I said only a mutant would come up with an n log n sort
intuitively, not that I did.  (Which doesn't exclude the possibility
that I'm a mutant, just not THAT kind of mutant :-) )

>"Pick and zot" doesn't do any movement at all, but leaves all the
>"zotted" entries in place to be skipped over on the next pass.
>It's good for sorting less than ten things.  ;-)  And it is _very_
>short.

Ah, OK, selection sort is basically the same thing but with exchanges.

for i = 1 to length
  for j = i + 1 to length
     if elem[i] < elem[j]  swap elem[i] with elem[j]
  next j
next i

Running time is O(n^2), all cases.
-- 
Matthew T. Russotto                            mrussotto@speakeasy.net
            June 20, 2003 is GIF Freedom Day (US)