Subject: Re: [stella] Bubble Sort From: "Andrew Davie" <adavie@xxxxxxxxxxx> Date: Tue, 26 Mar 2002 22:56:33 +1100 |
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/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: Aw: Re: Aw: Aw: Re: [stella] Bu, Thomas Jentzsch | Thread | Re: [stella] Bubble Sort, Thomas Jentzsch |
Re: [stella] Bubble Sort (Rodnay Za, Thomas Jentzsch | Date | Re: Aw: Re: Aw: Re: [stella] Sortin, Julian Squires |
Month |