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.9 required=5.0 tests=BAYES_00 autolearn=ham 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.228.227 with SMTP id sl3mr5796177pbc.5.1340145551587; Tue, 19 Jun 2012 15:39:11 -0700 (PDT) Path: l9ni70202pbj.0!nntp.google.com!news1.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: ggsub@pragmada.co.cc Newsgroups: comp.lang.ada Subject: Re: My Invention of "Bug Sort". Date: Tue, 19 Jun 2012 15:39:07 -0700 (PDT) Organization: http://groups.google.com Message-ID: <698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com> References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> NNTP-Posting-Host: 184.20.201.198 Mime-Version: 1.0 X-Trace: posting.google.com 1340145549 11371 127.0.0.1 (19 Jun 2012 22:39:09 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 19 Jun 2012 22:39:09 +0000 (UTC) In-Reply-To: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=184.20.201.198; posting-account=uInPWgoAAAD9VvUJDc0jNwDhBg_137JZ User-Agent: G2/1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Date: 2012-06-19T15:39:07-07:00 List-Id: 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 "Bug" in engineering is a euphemism for "error"; this usage goes back at le= ast to the 19th century. You might want to choose another name. > Q :=3D NextNum(I); > I_NUM(Q):=3D I_NUM(Q)+1; This is straightforward, and probably very good for your specific needs. Sp= ecialized sorting algorithms like this can do much better than general ones= . Like all specialized algorithms, this one has a number of shortcomings as= a general sorting algorithm, not least of which is its restriction to sort= ing values of discrete types only. It is hardly instantaneous. A complexity analysis is interesting: Most sorting algorithms' complexity analyses are based only on N, the numbe= r of values (the number of times Q gets a value in the example). This algor= ithm 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 call = this value M. M may be less than, equal to, or greater than N. For convenie= nce, I'll define B =3D Max (M, N) First, time complexity: The algorithm must initialize the array I_Num to al= l zeros; this is O(M). It then increments the corresponding value of I_Num = 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 overall= time complexity is O(B). Linear time complexity, which is very good. No ge= neral sorting algorithm is linear. 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_N= um into the corresponding sorted sequence. For example, if you're sorting t= he 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. For the following discussions, I'll presume the following declarations: Q : TQ; I_Num : array (TQ) of TI; An implementation of this must take into account a number of factors specif= ic to the problem being solved. TI must be large enough to hold the maximum= number of times a given value of Q may occur, but small enough that I_Num = can be declared. If a component of I_Num overflows, you'll either get incor= rect results (TI is a modular integer type) or and exception (TI is a signe= d integer type). I_Num'Size will be 2 ** (TQ'Size + TI'Size); that must fit in memory. If pa= rts of I_Num have to be swapped to disk, this could result in absolute time= s slower than a general, in-place algorithm. This could also be slower if M >> N. This is a form of insertion sort, in which values are sorted as they are en= countered. In this it is similar to an ordered-tree insertion sort, in whic= h values are inserted into an ordered, balanced, binary tree (or equivalent= structure) as they are encountered. This is another general sorting algori= thm that is O(N log N). An interesting approach, and probably well suited to your specific problem = area, but I doubt it will replace general sort algorithms.