[Coco] quicker bubble sort?

[Theodore Evans (Alex)]

On Jan 20, 2004, at 12:51 PM, KnudsenMJ at aol.com wrote:

> In a message dated 1/20/04 12:47:50 AM Eastern Standard Time,
> rtaylor at bayou.com writes:
>
>> Knowing that the largest value always floats to the very top on each 
>> pass,
>>  we can avoid having to scan the entire screen or table of data on 
>> each
>>  pass.  Instead, the table size is reduced by 1 byte on each pass.  
>> The
>>  overhead looks to be insignificant.
>
> Yes, this is a standard trick in writing a bubble sort -- don't 
> process the
> values you have already bubbled to the top.  It cuts the time by a 
> factor of
> two.
>
> Of course a bubble sort still takes Order(N**2) time (goes up with the 
> square
> of number of elements).  But for sorting short lists, it can't be beat 
> for
> simplicity.

I have seen a proof that any sort which only compares adjacent cannot 
be faster than O(n**2) (in _The Art of Computer Programming: Volume 3_ 
by Knuth, second edition).

You can also modify the bubble sort so that on each pass it keeps track 
of the first and last swap, and only runs from first-1 (or element 0) 
to last-1.  Unfortunately this adds overhead so that in many cases the 
performance gain beyond the last-passes is only marginal.  Another good 
variation is to forward if you don't swap (or are at the beginning) and 
backward otherwise.

ix=start
while ix<end
   if @(ix)>@(ix+1) then
     swap(@(ix), @(ix+1))
     if ix==start then
       ix=ix+1
     else
       ix=ix-1
     endif
   else
     ix=ix+1
   endif
wend

This is pseudo code, not any particular language.