Re: My Invention of "Bug Sort".

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

On Tuesday, June 19, 2012 12:55:12 PM UTC+1, Peter C. Chapin wrote:
> On 2012-06-19 03:13, 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.
> 
> I find your style of writing difficult to understand. However, if I 
> follow what you are saying, you are talking about Radix Sort. That 
> sorting method is O(n) instead of O(n log(n)) (which is the best 
> attainable running time for a comparison sort). However in general it 
> can have huge memory requirements and is really only practical in 
> special cases.
> 
> 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 compared 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 the 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 integers so you can see why my pre-occupation is with integers. 

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