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: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: Ted Dennison Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/23 Message-ID: <321DA569.41C67EA6@escmail.orl.mmc.com>#1/1 X-Deja-AN: 176014954 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <4uah1k$b2o@solutions.solon.com> <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> <4udb2o$7io@solutions.solon.com> <4uvi6j$1brg@watnews1.watson.ibm.com> <321886DA.15FB7483@escmail.orl.mmc.com> <4vjtaa$6bq@goanna.cs.rmit.edu.au> 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-23T00:00:00+00:00 List-Id: Richard A. O'Keefe wrote: > > Ted Dennison writes: > > >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). > > There is another factor: heap sort requires moving one's attention from > card [i] to card [i/2]; this is a very expensive operation for people. > The only way I would be able to do it with any reasonable speed is to > write the indices on the table and scan for a match instead of counting. The way I did it was to actually build a (pyramid-shaped) heap. Anything else would just be too error prone, given a time to beat. That's why I said it took a LOT of table space. 21 cards on the bottom, 16 on the next level, 8 on the next, etc. > The moral of the story is that the cost of the elementary operations > scales differently for humans, so that the "card sorting" trial cannot > be relied to tell you very much about how various sorts behave inside > a very different mechanism. (Polynomial -> polynomial; that's about all.) Exactly. For humans, comparisons are several factors faster than moves. So comparisons would have to seriously outnumber moves before you'd see the kind of time-behavior predicited by comparison-based analysis. -- T.E.D. (who just passed his algorithms course with a B) | Work - mailto:dennison@escmail.orl.mmc.com | | Home - mailto:dennison@iag.net | | URL - http://www.iag.net/~dennison |