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.4 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FORGED_MUA_MOZILLA,FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f6c360ce344b2364 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,CP1252 Received: by 10.68.220.230 with SMTP id pz6mr20501585pbc.3.1340146588257; Tue, 19 Jun 2012 15:56:28 -0700 (PDT) Path: l9ni70258pbj.0!nntp.google.com!news2.google.com!news4.google.com!feeder1.cambriumusenet.nl!feed.tweaknews.nl!195.62.100.242.MISMATCH!newsfeed.kamp.net!newsfeed.kamp.net!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!news.cgarbs.de!news.addix.net!feed.news.schlund.de!schlund.de!news.online.de!not-for-mail From: Martin Trenkmann Newsgroups: comp.lang.ada Subject: Re: My Invention of "Bug Sort". Date: Wed, 20 Jun 2012 00:56:27 +0200 Organization: 1&1 Internet AG Message-ID: References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> NNTP-Posting-Host: erft-4d07fa97.pool.mediaways.net Mime-Version: 1.0 X-Trace: online.de 1340146587 7661 77.7.250.151 (19 Jun 2012 22:56:27 GMT) X-Complaints-To: abuse@einsundeins.com NNTP-Posting-Date: Tue, 19 Jun 2012 22:56:27 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.4) Gecko/20120510 Icedove/10.0.4 In-Reply-To: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit Date: 2012-06-20T00:56:27+02:00 List-Id: On 06/19/2012 09:13 AM, Austin Obyrne wrote: > Copyright � 2012 Austin O'Byrne. > > Let us say that �NextNum� is a variable in a program output string that the user wants to sort at the end of the program run. > > How it works. > > Each change in �NextNum� is trapped as it is computed by a �bug� strategically placed in the lines of source code. > > Q := NextNum(I); > I_NUM(Q):= I_NUM(Q)+1; > > (This is the bug) > > The bug �gets� (captures) the instantaneous value of NextNum as it materializes and then immediately writes this instantaneous value to a dedicated array in order of *magnitude and returns for the next i.e. each value indexes its own place in the array ( *not in sequential order where the entries would be contiguous and remain unsorted � this is the most salient point for the reader to note). > > *This is defacto sorting per se. > > It only needs to read back from the array to see the sorted string which can be anything up to 1 million or more elements sorted in a split second, to complete the task. > > Discussion. > > Although I do not yet have performance figures to hand I think I can safely say that this is super quick, super efficient sorting. > > The method is hugely intrinsic to Ada and should be considered as a permanent part of the language mathematical library like say the �vector cross product�, trig functions, and calculus. I am proposing that idea here and now if any reader wants to get behind it with me to promote the idea further to the powers that be in Ada. I am retaining the copyright meanwhile. > > I cannot see any of the synthetic algorithms like �quick sort�, �tree sort� etc, coming even close to it. I think this blows them all right out of the water. > > I am developing the demonstration pilot programs (half way there) that I will be uploading to my site later for your perusal. > > There will be, > > 1) An interactive real-time, separate numerical and alphanumerical working program. > > 2) Batch working in numerical and alphanumerical � i.e. reading in from external unsorted files and out-putting to other sorted external files. > > A full description document will accompany the four uploaded programs in Ada that will have the compiler with them and are for free downloading. > > I would like to corner this invention as being fundamentally an Ada feature � you guys should get behind it now if you know how to contact the Ada people who have the power to make changes to the language � I don�t. > > With both feet firmly on the ground I say this �sort� method could become ubiquitous in the future and /or a bench mark for all other sort programs if they still exist. > > Enjoy, > > Austin O�Byrne ( aka - adacrypt). I think your approach is known as Bitmap Sort, which was originally described by John Bentley in his famous book "Programming Pearls". Try a Google search for it or just check out my first two hits: http://designingefficientsoftware.wordpress.com/2011/03/31/bitmap-sort/ http://www.stoimen.com/blog/2010/06/25/friday-algorithms-sorting-a-set-of-integers-far-quicker-than-quicksort/ Kind regards, Martin Trenkmann