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: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/23 Message-ID: <4vjtaa$6bq@goanna.cs.rmit.edu.au>#1/1 X-Deja-AN: 175983583 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> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada nntp-posting-user: ok Date: 1996-08-23T00:00:00+00:00 List-Id: 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). I would expect a two-handed swap to be about 3 times as fast as a one-handed swap. I just tried it with CDs, having a stack of them handy, and I can swap two CDs with two hands a little bit *more* than three times as fast as I can with one hand. (I don't know why it's more than 3x faster, it may just be the awkwardness of doing anything one-handed.) So one-handed -vs- two-handed might make a very big difference. 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. In contrast, insertion sort requires _no_ human counting, just move left one and detect end of sequence, and depending on the size of the cards, can benefit from a "block move". (With a standard card deck, I could probably move >5 cards up a position at once.) 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.) For what it's worth, if I am sorting a shuffled deck of cards, I lay out four rows of Ace..King and simply move each card straight to its right place. This is a bucket sort of the numbers 1..52 into 52 buckets. You can't do any better than that. But what does that tell you about sorting very large numbers of items, or items that are not numbers? -- Australian citizen since 14 August 1996. *Now* I can vote the xxxs out! Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.