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.6 required=5.0 tests=BAYES_00,DATE_IN_PAST_03_06, FORGED_HOTMAIL_RCVD2,FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,e0c23e7a19a435c4 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 ry3mr4910618pbc.8.1340496457618; Sat, 23 Jun 2012 17:07:37 -0700 (PDT) Path: l9ni12454pbj.0!nntp.google.com!news2.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Austin Obyrne Newsgroups: comp.lang.ada Subject: =?windows-1252?Q?Re=3A_Recapping_on_=93Bug_Sort=94=2E?= Date: Sat, 23 Jun 2012 13:49:02 -0700 (PDT) Organization: http://groups.google.com Message-ID: <43b8ea67-6204-41c9-8bcc-a14822709c77@googlegroups.com> References: <169bdbcb-cb43-4db9-9d48-3be2a88473eb@googlegroups.com> <77963856-3a25-4477-9510-769df7a9b85c@googlegroups.com> NNTP-Posting-Host: 31.52.108.135 Mime-Version: 1.0 X-Trace: posting.google.com 1340496457 19599 127.0.0.1 (24 Jun 2012 00:07:37 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sun, 24 Jun 2012 00:07:37 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=31.52.108.135; posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg User-Agent: G2/1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-06-23T13:49:02-07:00 List-Id: On Saturday, June 23, 2012 9:12:59 PM UTC+1, Niklas Holsti wrote: > On 12-06-23 22:07 , Austin Obyrne wrote: > > On Saturday, June 23, 2012 7:05:56 PM UTC+1, Niklas Holsti wrote: > >> On 12-06-23 13:20 , Austin Obyrne wrote: > >>> On Saturday, June 23, 2012 8:54:52 AM UTC+1, Austin Obyrne > >>> wrote: > >>>> On Friday, June 22, 2012 9:45:53 PM UTC+1, Jeffrey Carter > >>>> wrote: > >>>>> On 06/22/2012 12:55 PM, Austin Obyrne wrote: > >>>>>> > >>>>>> I have been told that my program resembles a known sort > >>>>>> program called =93Counting Sort=94. I would hate to be guilty > >>>>>> of plagiarism and I would like to point out therefore that > >>>>>> the salient thing about my =93Parallel Sort=94 is that my > >>>>>> implementation is geared to capturing data during any > >>>>>> unrelated program run-time and assigning the data in such a > >>>>>> way that the separate elements index their own addresses in > >>>>>> the sorting arrays. A similarity with some other existing > >>>>>> paper algorithm is simply fortuitous. > >>>>> > >>>>> What you have presented is an implementation of counting > >>>>> sort, nothing more. There is nothing new or unique about your > >>>>> implementation. > >> > >> Austin, > >> > >> While I agree with Jeff that you have rediscovered Counting Sort, > >> this does not mean that you are being accused of plagiarism. It is > >> common for programmers to rediscover algorithms that are basically > >> simple, but very good for some special cases -- and perhaps for > >> just these reasons are not very well known. > > > > Thanks for that. > > > > The very salient thing that everybody is missing is the way the data > > is collected and sorted simultaneously in "Parallel Sort" compared to > > Count Sort. >=20 > Yes, it is a neat feature of Counting Sort that the first step of the=20 > sort -- adding the values to the "count" array -- can be done for each=20 > new value separately, independently of the other values (since it is not= =20 > a comparison sort). Only the second step, the final scan of the "count"= =20 > array and output of the values in sorted order, must be delayed until=20 > all values are present. >=20 > This means, as you say, that the program can do the first step (add to=20 > "count" array) immediately when a new value is generated; it is not=20 > necessary to first collect all the values in some list, say, and then=20 > sort them. >=20 > But I don't think that the group is "missing" this fact; rather, we see= =20 > that it does not change the order of complexity (big-oh) of the=20 > algorithm, so it is not very interesting. >=20 > In fact, I'm not at all sure that adding the new values to the "count"=20 > array immediately is faster than first collecting them in a dense,=20 > unordered structure (array or list) and then sorting them. The frequent= =20 > scattered references to the large "count" array can stress the data=20 > cache and virtual memory system, perhaps causing more data-cache misses= =20 > and page faults which could make the program run slower. >=20 > > If I asked you to demonstrate "Count Sort" being used to sort a > > specimen set of data how would you go about making the data available > > to the program. >=20 > This is not an interesting question, again because the complexity of=20 > writing out and reading in a list of N integers is linear, O(N), in the= =20 > number of integers. >=20 > > Somewhere along the line you would have to prepare an external batch > > file for reading in or you would key in the data interactively >=20 > I can't make head or tail of that. You seem not to know how one can pass= =20 > data from one part of a program to another, or from one program to=20 > another, without human intervention. >=20 > > The counting part is trivial. It is the capturing concept that is > > the important difference between what I am calling Parallel Sort and > > what anyone else may call Count Sort . The counting is almost benign > > when the elements of data index their own addresses in an array in > > both cases. >=20 > My view is the opposite. The "capturing" is just normal programming,=20 > passing data from here to there within a program. Adding the data to the= =20 > "count" array at once may or may not be an advantage for speed, see=20 > above. From the point of view of the sorting problem, the central point= =20 > in Counting Sort is the "count" array that is indexed directly by the=20 > values to be sorted. *When* then values are added to the array is not=20 > imporant, IMO. >=20 > --=20 > Niklas Holsti > Tidorum Ltd > niklas holsti tidorum fi > . @ . Many thanks for all the contributions. I am drawing a line under this topi= c now. I gather from your last communique that Count Sort is also an embedd= ed sort program identical to the use I envisaged for my Parallel Sort. I h= ad decided that this was generally not the case and Count Sort was used int= eractively only in say academia (with full respect to academia). Apparentl= y I was wrong there. Many thanks again for your help in this entire matter. Austin.