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,f6c360ce344b2364 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,UTF8 Received: by 10.204.132.81 with SMTP id a17mr2365195bkt.4.1340110977143; Tue, 19 Jun 2012 06:02:57 -0700 (PDT) Path: e27ni66220bkw.0!nntp.google.com!news2.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Austin Obyrne Newsgroups: comp.lang.ada Subject: Re: My Invention of "Bug Sort". Date: Tue, 19 Jun 2012 06:01:03 -0700 (PDT) Organization: http://groups.google.com Message-ID: <81bb48ff-9374-47be-9d95-90afbdd1c010@googlegroups.com> References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> NNTP-Posting-Host: 86.167.60.110 Mime-Version: 1.0 X-Trace: posting.google.com 1340110976 9906 127.0.0.1 (19 Jun 2012 13:02:56 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 19 Jun 2012 13:02:56 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=86.167.60.110; posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg User-Agent: G2/1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-06-19T06:01:03-07:00 List-Id: On Tuesday, June 19, 2012 12:55:12 PM UTC+1, Peter C. Chapin wrote: > On 2012-06-19 03:13, Austin Obyrne wrote: >=20 > > Copyright =EF=BF=BD 2012 Austin O'Byrne. > > > > Let us say that =EF=BF=BDNextNum=EF=BF=BD is a variable in a program ou= tput string that the user wants to sort at the end of the program run. > > > > How it works. > > > > Each change in =EF=BF=BDNextNum=EF=BF=BD is trapped as it is computed b= y a =EF=BF=BDbug=EF=BF=BD strategically placed in the lines of source code. > > > > Q :=3D NextNum(I); > > I_NUM(Q):=3D I_NUM(Q)+1; > > > > (This is the bug) > > > > The bug =EF=BF=BDgets=EF=BF=BD (captures) the instantaneous value of Ne= xtNum as it materializes and then immediately writes this instantaneous val= ue 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 =EF=BF=BD this i= s 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 whic= h can be anything up to 1 million or more elements sorted in a split second= , to complete the task. >=20 > I find your style of writing difficult to understand. However, if I=20 > follow what you are saying, you are talking about Radix Sort. That=20 > sorting method is O(n) instead of O(n log(n)) (which is the best=20 > attainable running time for a comparison sort). However in general it=20 > can have huge memory requirements and is really only practical in=20 > special cases. >=20 > Peter Hi Peter, I have never heard of Radix Sort unitl you mention it now so I have checked= it out on Wikipedia just to get an impression of how it works when compare= d to my Bug Sort. That's a truly tortuous algorithm and I can see where the memory goes. I only deal with whole numbers - integers and alphanumeric characters and t= he memory consumption is very much smaller - 10 megabytes does an awful lot= of sorting i.e in normal situations this is quite little. My interest is largely in cryptography which never uses anything but intege= rs so you can see why my pre-occupation is with integers.=20 There is no comparison as far as I can see between Radix Sort and Bug Sort = but I take your point that something taht sorts float values on a basis of = signicficant values must require a lot of memory. If I had that problem I would look for a better solution beforehand. Many thanks for your useful pointer. Regards - Austin O'Byrne