[Coco] quicker bubble sort?

KnudsenMJ at aol.com KnudsenMJ at aol.com
Tue Jan 20 17:51:02 EST 2004


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.

The C Libraries for OS-9, Linux, and Unix all have a qsort() function that is 
amazingly fast, though messy to call.  Not sure if the 6809 version has it, 
would have to look at Coco3 UltiMusE code to be sure.  --Mike K.



More information about the Coco mailing list