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.4 required=5.0 tests=BAYES_00,FORGED_MUA_MOZILLA 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.238.65 with SMTP id vi1mr7906168pbc.7.1340475447085; Sat, 23 Jun 2012 11:17:27 -0700 (PDT) Path: l9ni11531pbj.0!nntp.google.com!news1.google.com!news3.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Niklas Holsti Newsgroups: comp.lang.ada Subject: Re: Recapping on =?windows-1252?Q?=93Bug_Sort=94=2E?= Date: Sat, 23 Jun 2012 21:17:24 +0300 Organization: Tidorum Ltd Message-ID: References: <169bdbcb-cb43-4db9-9d48-3be2a88473eb@googlegroups.com> <77963856-3a25-4477-9510-769df7a9b85c@googlegroups.com> <5324c10f-52f2-4f23-ac44-cd1bc9fa580d@googlegroups.com> Mime-Version: 1.0 X-Trace: individual.net J4qsjUjOPTHFPu7Yg2NxYgK7wL5SAVEmIt2x2yap/kBG5qjdPR5pEm0DK3O+y5vf6c Cancel-Lock: sha1:umI/Rr8UYHBbKWt+z9ZtB/2pdpw= User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:12.0) Gecko/20120428 Thunderbird/12.0.1 In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit Date: 2012-06-23T21:17:24+03:00 List-Id: 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 called >>>>>> �Counting Sort�. I would hate to be guilty of plagiarism and I would like to >>>>>> point out therefore that the salient thing about my �Parallel Sort� 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. > ... > > 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.) The times are not so good. I ran the following command on my MacBook Air (old model, not a superfast machine); this command generates a text file with 85500 7-digit numbers in a more or less mixed order and sorts it into descdending order with the Unix "sort" program: yes | head -85500 | pr -n:7 -t | cut -d: -f1 | tr ' 0123456789' '09472601583' | (time sort -n -r >sorted) The output from the "time" command that measures the "sort" process is: real 0m0.133s user 0m0.068s sys 0m0.011s This means that even the elapsed time, including all the I/O, is only 0.133 seconds. Note that the "sort" program is a very general one, so it should have lots of overhead compared to a program written to sort only a set of integers. If your program handles 7-digit integers, your "count" array will have 10 million elements. Most of the time taken by your program will be spent in initializing the array to "all zero" and in scanning the array from start to end to pick up and output the 85500 numbers, which fill less than 1% of the array. This is the drawback of the Counting Sort method: if the data is sparse in its range, there is lots of overhead both in time and memory usage. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .