From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: * X-Spam-Status: No, score=1.6 required=5.0 tests=BAYES_05,INVALID_MSGID, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public From: Lawrence Kirby Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/13 Message-ID: <839939925snz@genesis.demon.co.uk>#1/1 X-Deja-AN: 173924497 x-nntp-posting-host: genesis.demon.co.uk references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> x-mail2news-path: genesis.demon.co.uk organization: none reply-to: fred@genesis.demon.co.uk newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-13T00:00:00+00:00 List-Id: In article eachus@spectre.mitre.org "Robert I. Eachus" writes: >In article <839708378snz@genesis.demon.co.uk> Lawrence Kirby > writes: > > I said: > > >Quicksort step of picking up the cards is O(n), not O(n log n) > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > > In article <839708378snz@genesis.demon.co.uk> Lawrence Kirby > writes: > > > What does this phrase mean? Quicksort is an (n log n) (average time) > > operation. Building a heap is an O(n) operation. > > It means that when you finish the first stage of the Quicksort, you >have several piles laid out on the table. Completing the sort >requires picking them up in order. Then you have to sort each pile recursively bringing you back to O(n log n). Picking up a pile of cards isn't what determines the running time of quicksort. For heap sort, building the heap >is also an O(n log n) operation, since you maintain a heap. Wrong, you don't maintain a heap, you just build it. If you approach that correctly it is an O(n) operation. Quoting from Sedgewick: "... its can in fact be proven that the construction process takes linear time since so many small heaps are processed". > However >picking up the cards is also N log N since you have to maintain the >heap property, and in any case you pick them up one at a time. However there is a lot more to quicksort than just "picking up the cards". > Try the experiment. A good heapsorter will finish heapifying and >pick up the first card first. A couple seconds later, the quicksorter >will finish the job, assuming the cards were well shuffled. I did. It took slightly over twice as long to quicksort a pack of 52 playing cards than it did to create a heap from them. The only real thing of note is that you can perform the individual operations required for partitioning much quicker than the careful card repositioning you need to perform to construct a heap. That does reflect to some extent the respective computer implementations but the effect is much more pronounced with cards. Overall building a heap required far fewer operations than the quicksort. (Of >course, one of the fun steps is to tell the students to repeat the >exercise--without shuffling. Now the race is between quicksort and >bubblesort for last place.) With cards it is easy to implement a random or an approximate half way pivot selection. Which prings up the question of precisely what algorithms are actually being used. Further discussion of this ought to go to a newsgroup such as comp.programming or via email. -- ----------------------------------------- Lawrence Kirby | fred@genesis.demon.co.uk Wilts, England | 70734.126@compuserve.com -----------------------------------------