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^2N)). (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 