Re: My Invention of "Bug Sort".

[Austin Obyrne <austin.obyrne@hotmail.com>]

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:
> > 
> > Each change in ‘NextNum’ is trapped as it is computed by a ‘bug’ strategically placed in the lines of source code. 
> 
> "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.
> 
> > Q := NextNum(I);
> > I_NUM(Q):= I_NUM(Q)+1;
> 
> This is straightforward, and probably very good for your specific needs. Specialized 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 sorting 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 number of values (the number of times Q gets a value in the example). This algorithm 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 convenience, I'll define
> 
> B = Max (M, N)
> 
> 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_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 general 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_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 => 1, 2 => 3, 3 => 7). Such a sequence is O(N). So the space complexity is at least 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 specific 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 incorrect results (TI is a modular integer type) or and exception (TI is a signed integer type).
> 
> 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 times 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 encountered. In this it is similar to an ordered-tree insertion sort, in which values are inserted into an ordered, balanced, binary tree (or equivalent structure) as they are encountered. This is another general sorting algorithm 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.



<< 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 worms 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 requires 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. 

Many thanks for your excellent and informed analysis.

Austin O'Byrne

Many thanks for your excellent analysis