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,e0c23e7a19a435c4 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,CP1252 Received: by 10.68.219.170 with SMTP id pp10mr8173479pbc.1.1340479404168; Sat, 23 Jun 2012 12:23:24 -0700 (PDT) Path: l9ni11704pbj.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 12:21:52 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <169bdbcb-cb43-4db9-9d48-3be2a88473eb@googlegroups.com> <77963856-3a25-4477-9510-769df7a9b85c@googlegroups.com> <5324c10f-52f2-4f23-ac44-cd1bc9fa580d@googlegroups.com> NNTP-Posting-Host: 31.52.108.135 Mime-Version: 1.0 X-Trace: posting.google.com 1340479404 8542 127.0.0.1 (23 Jun 2012 19:23:24 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sat, 23 Jun 2012 19:23:24 +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-23T12:21:52-07:00 List-Id: On Saturday, June 23, 2012 7:17:24 PM UTC+1, Niklas Holsti wrote: > On 12-06-23 17:21 , Austin Obyrne wrote: > > On Saturday, June 23, 2012 2:08:58 PM UTC+1, Austin Obyrne wrote: > >> On Saturday, June 23, 2012 11:20:10 AM UTC+1, 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 ca= lled > >>>>>> =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 So= rt=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 el= ements > >>>>>> index their own addresses in the sorting arrays. A similarity wit= h some > >>>>>> other existing paper algorithm is simply fortuitous. > >>>>> > >>>>> What you have presented is an implementation of counting sort, noth= ing more. > >>>>> There is nothing new or unique about your implementation. > > ... > > > > Final update on performance. > > > > These are the results: > > > > 14250 seven-digit positive integers 1 - 2 secs > > > > 28500 "" "" "" "" 1 - 2 secs > > > > 42750 "" "" "" "" 1 - 2 secs > > > > 85500 "" "" "" "" 2 - 3 secs > > > > Austin O'Byrne. > > Clearly, these are extraordinary times for a sort program. > > (the measuring method isn't sensitive enough to give more exact times.) >=20 > The times are not so good. I ran the following command on my MacBook Air= =20 > (old model, not a superfast machine); this command generates a text file= =20 > with 85500 7-digit numbers in a more or less mixed order and sorts it=20 > into descdending order with the Unix "sort" program: >=20 > yes | head -85500 | pr -n:7 -t | cut -d: -f1 | tr ' 0123456789'=20 > '09472601583' | (time sort -n -r >sorted) >=20 > The output from the "time" command that measures the "sort" process is: >=20 > real 0m0.133s > user 0m0.068s > sys 0m0.011s >=20 > This means that even the elapsed time, including all the I/O, is only=20 > 0.133 seconds. Note that the "sort" program is a very general one, so it= =20 > should have lots of overhead compared to a program written to sort only= =20 > a set of integers. >=20 > If your program handles 7-digit integers, your "count" array will have=20 > 10 million elements. Most of the time taken by your program will be=20 > spent in initializing the array to "all zero" and in scanning the array= =20 > from start to end to pick up and output the 85500 numbers, which fill=20 > less than 1% of the array. This is the drawback of the Counting Sort=20 > method: if the data is sparse in its range, there is lots of overhead=20 > both in time and memory usage. >=20 > --=20 > Niklas Holsti > Tidorum Ltd > niklas holsti tidorum fi > . @ . Sorry, I missed half your message before I started writing - it is still su= bstantially true I believe - *you were able to generate a test program quic= kly in order to test the run time but how in the real world would you input= the data from another source i.e. beyond your control, to your 'Count Sort= ' program. It would have to be keyed in somewhere by a human operator??=20 Cheers.=20 Austin.