[Coco] 6809 example

[Theodore Evans (Alex)]

On Jan 17, 2004, at 6:20 PM, Roger Taylor wrote:

> At 01:50 PM 1/17/2004 -0500, you wrote:
>> Note that even though the code is more complex, the speed is much 
>> much faster than the bubble sort. By implication this also means that 
>> if speed is your primary concern in picking a language, think again! 
>> The algorithm and quality of coding can be more important than the 
>> language.

> That looks like more than a handful for a beginner, especially the LOG 
> functions.  I think a Hello World to stdout would be a very good 1st 
> example.

Well, int(2^int(log(512)/log(2))-1)=511 and the outermost int is 
superflous since 2 raised to an integer power will be an integer.  I 
agree that this would be a poor first program (in any language).

Some people claim that the Bubble sort is the slowest sort algorithm.  
Barden used a O(n^2) version of the bubble sort.  There is an O(n^3) 
version of the bubble sort.  Both of these are worst case times.  The 
bubble sort can perform much better with partially sorted lists.  If 
you add m elements to a sorted list of length n then it is O(m.n) 
assuming that m is less than log2(n) this is better than the O(n log n) 
of the high efficiency (single processor) sort algorithms.  Of course 
if you sort the data to be added then merge the two sorted lists as is 
done in the merge sort (another O(n log n) sort algorithm) you will get 
even better performance.  As a silly exercise while in college I 
devised a "reasonable" sort algorithm which was to be as inefficient as 
possible (ignoring such oddities as the random sort which has 
non-determinate running time)  this "slow" sort had O(n^n) running 
time.