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,CP1252 Received: by 10.68.219.170 with SMTP id pp10mr21972237pbc.1.1340181165242; Wed, 20 Jun 2012 01:32:45 -0700 (PDT) Path: l9ni71744pbj.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: Wed, 20 Jun 2012 01:32:44 -0700 (PDT) Organization: http://groups.google.com Message-ID: <5c5aa9d4-fcfe-46fb-9b85-762518651455@googlegroups.com> References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> <698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com> NNTP-Posting-Host: 86.171.156.227 Mime-Version: 1.0 X-Trace: posting.google.com 1340181165 22974 127.0.0.1 (20 Jun 2012 08:32:45 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Wed, 20 Jun 2012 08:32:45 +0000 (UTC) In-Reply-To: <698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=86.171.156.227; posting-account=pmkN8QoAAAAtIhXRUfydb0SCISnwaeyg User-Agent: G2/1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-06-20T01:32:44-07:00 List-Id: On Tuesday, June 19, 2012 11:39:07 PM UTC+1, (unknown) wrote: > On Tuesday, June 19, 2012 12:13:28 AM UTC-7, Austin Obyrne wrote: > >=20 > > Each change in =91NextNum=92 is trapped as it is computed by a =91bug= =92 strategically placed in the lines of source code.=20 >=20 > "Bug" in engineering is a euphemism for "error"; this usage goes back at = least to the 19th century. You might want to choose another name. >=20 > > Q :=3D NextNum(I); > > I_NUM(Q):=3D I_NUM(Q)+1; >=20 > This is straightforward, and probably very good for your specific needs. = Specialized sorting algorithms like this can do much better than general on= es. Like all specialized algorithms, this one has a number of shortcomings = as a general sorting algorithm, not least of which is its restriction to so= rting values of discrete types only. >=20 > It is hardly instantaneous. A complexity analysis is interesting: >=20 > Most sorting algorithms' complexity analyses are based only on N, the num= ber of values (the number of times Q gets a value in the example). This alg= orithm must also take into account the number of possible values Q may have= . If Q is of type T, this is T'Pos (T'Last) - T'Pos (T'First) + 1. I'll cal= l this value M. M may be less than, equal to, or greater than N. For conven= ience, I'll define >=20 > B =3D Max (M, N) >=20 > First, time complexity: The algorithm must initialize the array I_Num to = all zeros; this is O(M). It then increments the corresponding value of I_Nu= m for each value of Q encountered; this is O(N). Finally, it must traverse = I_Num to do something with the resulting values; this is O(M). So the overa= ll time complexity is O(B). Linear time complexity, which is very good. No = general sorting algorithm is linear. >=20 > Now space complexity: The algorithm needs the space for I_Num, which is O= (M). Depending on what you do with the results, you may need to transform I= _Num into the corresponding sorted sequence. For example, if you're sorting= the values (3, 7, 1), you often want to end up with an array (1 =3D> 1, 2 = =3D> 3, 3 =3D> 7). Such a sequence is O(N). So the space complexity is at l= east O(M), and may be O(N) (if that's larger). To be safe for all cases we = must call it O(B). Several sorting algorithms have O(N) space requirements,= so that's not necessarily a problem. >=20 > For the following discussions, I'll presume the following declarations: >=20 > Q : TQ; > I_Num : array (TQ) of TI; >=20 > An implementation of this must take into account a number of factors spec= ific to the problem being solved. TI must be large enough to hold the maxim= um number of times a given value of Q may occur, but small enough that I_Nu= m can be declared. If a component of I_Num overflows, you'll either get inc= orrect results (TI is a modular integer type) or and exception (TI is a sig= ned integer type). >=20 > I_Num'Size will be 2 ** (TQ'Size + TI'Size); that must fit in memory. If = parts of I_Num have to be swapped to disk, this could result in absolute ti= mes slower than a general, in-place algorithm. >=20 > This could also be slower if M >> N. >=20 > This is a form of insertion sort, in which values are sorted as they are = encountered. In this it is similar to an ordered-tree insertion sort, in wh= ich values are inserted into an ordered, balanced, binary tree (or equivale= nt structure) as they are encountered. This is another general sorting algo= rithm that is O(N log N). >=20 > An interesting approach, and probably well suited to your specific proble= m area, but I doubt it will replace general sort algorithms. << This is straightforward, and probably very good for your specific needs. I think this sums it up completely. I realise now that this is a can of wor= ms when taken as general sort program and probably no better than any other= . I think the fact that it works concurrently with the main program amd requi= res no extra handling of data after it has been computed is a plus?. Question: In a real world situation could this sort mechanism be done by a = 'tasking' package in Ada.=20 Many thanks for your excellent and informed analysis. Austin O'Byrne Many thanks for your excellent analysis