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: jdege@winternet.com (Jeff Dege) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/18 Message-ID: <4v68v8$6oc@blackice.winternet.com>#1/1 X-Deja-AN: 174906113 references: <4umeot$re2@hil-news-svc-2.compuserve.com> <4v2fb9$lpj@news.utdallas.edu> <4v2msb$4a8@krusty.irvine.com> <4v63js$iqp@news.utdallas.edu> followup-to: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada organization: StarNet Communications, Inc newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-18T00:00:00+00:00 List-Id: On Sun, 18 Aug 1996 03:43:52 GMT, Steve Heller (heller@utdallas.edu) wrote: : I'll accept your analysis as being correct theoretically. However, I : have never seen a real application where the maximum key length was : not both: : 1. known in advance and : 2. relatively small relative to the number of elements to be sorted. : Under those conditions, I believe O(n) is appropriate. Of course, I : welcome corrections if I have misstated something here. I've written code that was intended to work on keys of arbitrary length. True, in most actual uses of the code, the keys had fixed length, but the code couldn't depend upon that. I've had occassions to sort a couple of dozen strings of 80 characters, on occasion, as well. What I would consider to be closer to the truth is that if the maximum key length isn't both: 1. known in advance and 2. relatively small relative to the number of elements to be sorted, nobody would even consider radix sort. And so it falls quietly out of the set of cases you envision when you think about radix sorting. -- Nearly every electrical engineer believes deep in his heart that he is better at writing computer software than any computer programmer, and can show as proof the fact that he has written a number of small applications, each of which was done quickly, easily, and exactly met his needs.