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,8cb466bc329b6af9,start X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,CP1252 Received: by 10.68.223.73 with SMTP id qs9mr2607059pbc.7.1341314564027; Tue, 03 Jul 2012 04:22:44 -0700 (PDT) Path: l9ni10735pbj.0!nntp.google.com!news1.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Austin Obyrne Newsgroups: comp.lang.ada Subject: =?windows-1252?Q?More_on_the_=93Parallel_Sort=94_Data_Sorting_Program?= =?windows-1252?Q?=2E?= Date: Tue, 3 Jul 2012 04:22:43 -0700 (PDT) Organization: http://groups.google.com Message-ID: <0117b182-7d8f-40ab-8729-6eb258ba5616@googlegroups.com> NNTP-Posting-Host: 86.128.16.224 Mime-Version: 1.0 X-Trace: posting.google.com 1341314563 14549 127.0.0.1 (3 Jul 2012 11:22:43 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 3 Jul 2012 11:22:43 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=86.128.16.224; posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg User-Agent: G2/1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-07-03T04:22:43-07:00 List-Id: I am promoting this as a re-invention of =93Counting Sort=94 having being a= cquainted of the latter=92s existence by readers, something I was truly una= ware of but would like to point out that =93Counting =93 or =93Count sort= =94 was invented in 1954. I quote from Wikipedia, =93Although radix sorting itself dates back far longer, counting sort, and = its application to radix sorting, were both invented by Harold H. Seward in= 1954.=94 - Unquote =20 Given the state of progress in computer development at that time this inven= tion must surely have been more of a longhand algorithm than a computer dri= ven program concept. I am not an an ego-trip here but I think it=92s fair to say that my impleme= ntation of =93Parallel Sort=94 as a data sorting program written in Ada is = a quite different invention. Given that the algorithm is unique and cannot possibly be presented in some= identical but different form (similar to the distinctiveness of the factor= ing algorithm which is also a benchmark in computing)) I am claiming that t= his is a bench mark for future in data sorting techniques that might even b= e used as a yardstick in comparing computer and language combinations. I know that personally, I have supreme confidence that this is true of Ada. In the course of updating my background knowledge, I made a few =91almost= =92 right but not totally right statements that I would like to amend here = just in case. In the general macro study of complexity theory the highest order of a func= tion is taken as the Big O rating and the minor terms including constants a= re ignored. This is not true in data sorting theory =96 the constants cannot be ignored= . Example. I have said, 1) In the expression (n Lg n) for the =91worst case=92 scenario datum in co= mparison type sort methods, any base will be acceptable and,=20 2) Log(a) n =3D Log (b) n /Log(b) (a) =96 the constant Log(b)(a) can be ign= ored. These are both wrong statements in data sort theory, only (n Ln n) is corre= ct and if it is changed to a different base (pointless really) then the con= stant must be included. Example: Comparing my =93Parallel Sort=94 data sort program that has linear complexi= ty growth with =91n=92 increasing, to a comparison-based sort program as a = ratio of these two would be,=20 n; (n ln n)=20 or, 1; (Ln n) It would be totally worng if I was to instead say, 1; Log(b)(n) Clearly, changing the base of the logarithm without including the constant = of change would be wrong. Suppose I substituted, (Ln(n)) =3D (Log (b)(n) / log (b)(e)=20 as shown it would give a totally wrong comparison ratio not to include the= constant (Log(b)(e)) I contend also that this is the first implementation in any computer langua= ge of any version of =93Counting Sort) ever. I am mooting my invention of =93Parallel Sort=94 as a benchmark for future = i.e. =93Parallel Sort=94 in Ada is both a first in data sorting and a first= in any computer language.=20 I have written a few specimen comparison programs in Ada just for the hell = of it and there is such a great amount of user assistance by way of conditi= onal statements required in the source code that there is no case whatever = that can be argued for retaining these in the future - they are just totall= y redundant. It is time to move forward in another area of computational mathematics in = my view away from comparison sorting methods =96 they are no longer require= d. Austin O=92Byrne,