Whilst the discussion is interesting, I still think you guys *really* need
to read Knuth's work on sorting. I looked up his analysis of bubble sort,
and quote...
"Compared to straight insertion (Algorithm 5.2.1S), bubble sorting requires
a more complicated program and takes more than twice as long!" (pp.109)
His analysis of bubble sort (which gives you some idea of the degree of
complexity of his treatment of the subject) is summarised thus:
"To summarise our analysis of the bubble sort, the formulas derived above
and below may be written as follows:
A = (min 1, ave N- sqrt( piN/2 + O(1), max N); (10)
B = (min 0, ave 1/4(N^2 - N), max 1/2(N^2 - N)); (11)
C = (min N - 1, ave 1/2( N^2 - NlnN - (lambda + ln2 -1) N) + O(sqrt(n), max
1/2(N^2-N)). (12)
In each case the minimum occurs when the input is already in order, and the
maximum occurs when it is in reverse order; so the MIX running time is 8A +
7B + 8C + 1 = (min 8N + 1, ave 5.75N^2 + O(N log N), max 7.5N^2 + 0.5N +
1)."
MIX is a conceptual machine he uses to program sample code and see how it
all works. Though not particularly understandable without the rest of the
book, the above analysis of just this one sort shows why this book is
considered the absolute bible on computer programming. The above ONE
paragraph of his 780 page volume on sorting and searching! And that volume
is just one of 3 published so far.
-
Andrew Davie - adavie@xxxxxxxxxxx
TwoHeaded Software - www.2headed.com
----- Original Message -----
From: "Thomas Jentzsch" <tjentzsch@xxxxxx>
To: <stella@xxxxxxxxxxx>
Sent: Tuesday, March 26, 2002 10:36 PM
Subject: Re: Aw: Re: Aw: Aw: Re: [stella] Bubble Sort
> Manuel wrote:
> >Better you give me a shotgun than a shovel... :-)
>
> Sorry, but I run out of ammo several years ago. :-)
>
> Have fun!
> Thomas
>
>
> --------------------------------------------------------------------------
--------------------
> Archives (includes files) at http://www.biglist.com/lists/stella/archives/
> Unsub & more at http://www.biglist.com/lists/stella/
>
>
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
