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.0 required=5.0 tests=BAYES_00,FORGED_HOTMAIL_RCVD2, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,14addec9b7398575,start X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,CP1252 Received: by 10.68.227.67 with SMTP id ry3mr13207856pbc.8.1340721683843; Tue, 26 Jun 2012 07:41:23 -0700 (PDT) Path: l9ni22294pbj.0!nntp.google.com!news2.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Austin Obyrne Newsgroups: comp.lang.ada Subject: One More Word on "Count Sort" versus "Parallel Sort." Date: Tue, 26 Jun 2012 07:39:43 -0700 (PDT) Organization: http://groups.google.com Message-ID: <0e7625d4-28d5-4ae3-8597-0ae6f3a4b833@googlegroups.com> NNTP-Posting-Host: 109.157.196.196 Mime-Version: 1.0 X-Trace: posting.google.com 1340721683 11600 127.0.0.1 (26 Jun 2012 14:41:23 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 26 Jun 2012 14:41:23 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=109.157.196.196; posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg User-Agent: G2/1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-06-26T07:39:43-07:00 List-Id: I have done a bit of homework on the historical development of this sort pr= ogram now i.e. Count Sort and it behoves me to share the results with anybo= dy who is still interested. I have had a lot of friendly good advice from several readers and I can say= that all of what people have said comes true but ....(almost). Quote from Wikipedia. Although radix sorting itself dates back far longer, counting sort, and its= application to radix sorting, were both invented by Harold H. Seward in 19= 54.[1][4][8] : Unquote. The algorithm at that time cannot have been anything more than a desktop pa= per algorithm because computers didn=92t come into vogue until the 70=92s . I followed up =93Introduction to Programming =96 Vol 3 Sorting and Searchin= g 1998=94 by Donald Knuth which is supposed to be almost a seminal work giv= en the fame of the author but there is no mention of Count Sort in the cont= ents so I didn=92t buy the book - I had expected a discussion of Count Sort= and maybe a published computer program of it. His first edition of the bo= ok was in 1973 and given that =91C=92 and 'C++' were well established by 19= 98 one would have expected a published program in the =91C=92 or 'C++' prog= ramming languages in that later edition (if anybody knows of one please let= me know). A really good find was this title, =93Introduction to Algorithms=94 - T. Cormen, C. Leiserson, R. Rivest, C = Stein. I=92m going for this instead =96 it is written in pseudo code which= is very much easier to follow and it gives a lot of good mathematical proo= fs. For example why is O(n Log n) the lower bound for comparison sort programs = and much more that I found interetsing . I am pleased to be able to say =93It is rather neat the way my "Parallel So= rt" gets the first numbers before knowing any of the others=94. It goes st= raight for the jugular and consigns it preemptively to its proper address i= n the sorted array immediately it captures a value in the variable being mo= nitored. The traditional "Count Sort" does not do this and although it is not a comp= arison sort method per se it still does require some evaluation work before= indexing any element in the array - it appears to need to know what is com= ing next. I see this as a stumbling block to a fully embedded sort program= that can work in parallel and in current realtime with a second main progr= am. This is a plus for "Parallel Sort" because it does exactly that. It happens that Ada lends itself perfectly to this design of parallel sorti= ng program for embedding seamlessly with main programs that may contain any= number of variables for sorting. Cheers, Austin O=92 byrne. PS =96 Anybody care to expanded on (nlogn) - proof? What's the value of Ln n!(n factorial? Also, Any base is valid in this function. Clearly, any base will do because the constant that accompanies a change of= base is ignored in complexity theory. Example: Log(a)n =3D Log(b)n / lg(b)(a) lg(b)(a) is a constant that is independent of 'n' and does not affect the = =93order=94 of the complexity and can be ignored =3D> any base is valid.