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.3 required=5.0 tests=BAYES_00,INVALID_MSGID 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: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: Ted Dennison Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/19 Message-ID: <321886DA.15FB7483@escmail.orl.mmc.com>#1/1 X-Deja-AN: 175258713 references: <31FBC584.4188@ivic.qc.ca> content-type: text/plain; charset=us-ascii organization: Lockheed Martin Information Systems mime-version: 1.0 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada x-mailer: Mozilla 2.0 (X11; I; SunOS 4.1.3_U1 sun4m) Date: 1996-08-19T00:00:00+00:00 List-Id: > In article , dewar@cs.nyu.edu (Robert Dewar) writes: > > |> Robert Eachus says > |> > |> " I managed to do the "fun" experiment once. Take three students > |> and have them learn Quicksort, Heapsort, and Bubblesort on "small" > |> decks. At even 50 to 60 cards, the students doing Heapsort and > |> Quicksort are racing each other*, and the Bubblesort victim is still > |> hard at work well after they have finished." > |> > |> Try extending your experiment (I have also used this) a bit. Have a fourth > |> person sort the deck who knows none of these algorithms. That fourth > |> person will typically beat the Quicksort and Heapsort guys. Why? Because > |> the natural way to sort cards is with some physical embodiment of adress > |> calculation sorting, which can have an average time performance that is > |> order (N) rather than order N log N. > |> > |> This can be an instructive addition to your experiment! I had some time on my hands this weekend, so I tried this myself (On vacation at the beach with a broken arm, what else was I to do?) With no practice, quicksort on a deck of playing cards took me less than 5 minutes. After a bit of practice, heapsort still took me more than 15 minutes (and a LOT of table space). If you think about this exercise, comparisons take WAY less time than swaps (especially with one arm). So it would seem to me that you would need several decks of playing cards (each) to make it much of a race. -- T.E.D. | Work - mailto:dennison@escmail.orl.mmc.com | | Home - mailto:dennison@iag.net | | URL - http://www.iag.net/~dennison |