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=0.2 required=5.0 tests=BAYES_00,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: 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: ncohen@watson.ibm.com (Norman H. Cohen)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/15
Message-ID: <4uvi6j$1brg@watnews1.watson.ibm.com>#1/1
X-Deja-AN: 174377010
distribution: world
references: <31FBC584.4188@ivic.qc.ca>
organization: IBM T.J. Watson Research Center
reply-to: ncohen@watson.ibm.com
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-15T00:00:00+00:00
List-Id: <comp.lang.ada>


In article <dewar.839593893@schonberg>, 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!

If the set of keys on the card is dense (e.g. consecutive numbers from 1
to 60), then a radix sort (also O(n)) works nicely for 50-60 cards.
That how I sort my cancelled checks each month.

--
Norman H. Cohen    ncohen@watson.ibm.com