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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public From: heller@utdallas.edu (Steve Heller) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/18 Message-ID: <4v7ro4$ac@news.utdallas.edu>#1/1 X-Deja-AN: 174944547 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> <4umeot$re2@hil-news-svc-2.compuserve.com> <4v2fb9$lpj@news.utdallas.edu> <4v63jv$iqp@news.utdallas.edu> organization: The University of Texas at Dallas newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-18T00:00:00+00:00 List-Id: dewar@cs.nyu.edu (Robert Dewar) wrote: >Steve said >">No, they are much simpler to analyze, analyzing the left to right >>radix sort (the only reasonable implementation, the right to left sort >>is never a good choice), or the address calculation sort, is not easy. > Never? That's interesting, because it has very predictable behavior >and runs very quickly (given enough real memory)." >Well if the key is one digit, then of course you just have a counting >sort and it is fine, but if the key is any significant number of >digits, then NlogN < KN, e.g. 32 bit numbers with less than 2**32 >of them to sort! Well, let's see. If we have 2**24 elements of 32 bits each to sort, and we sort the keys two bytes at a time (64K elements in the counting table), then we have two passes to count and two to sort, so K is four. On the other hand, logN, for base 2, is 24. The latter is clearly 6 times the former, if the same time is required per operation, and I suspect that the operations in the distribution counting sort (especially the counting passes) are less complex than those in quicksort or heapsort. Steve Heller, author and software engineer http://ourworld.compuserve.com/homepages/steve_heller