Re: Recapping on “Bug Sort”.

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

On Saturday, June 23, 2012 7:05:56 PM UTC+1, Niklas Holsti wrote:
> On 12-06-23 13:20 , Austin Obyrne wrote:
> > On Saturday, June 23, 2012 8:54:52 AM UTC+1, Austin Obyrne wrote:
> >> On Friday, June 22, 2012 9:45:53 PM UTC+1, Jeffrey Carter wrote:
> >>> On 06/22/2012 12:55 PM, Austin Obyrne wrote:
> >>>>
> >>>> I have been told that my program resembles a known sort program called
> >>>> “Counting Sort”.  I would hate to be guilty of plagiarism and I would like to
> >>>> point out therefore that the salient thing about my “Parallel Sort” is that
> >>>> my implementation is geared to capturing data during any unrelated program
> >>>> run-time and assigning the data in such a way that the separate elements
> >>>> index their own addresses in the sorting arrays.  A similarity with some
> >>>> other existing paper algorithm is simply fortuitous.
> >>>
> >>> What you have presented is an implementation of counting sort, nothing more.
> >>> There is nothing new or unique about your implementation.
> 
> Austin,
> 
> While I agree with Jeff that you have rediscovered Counting Sort, this 
> does not mean that you are being accused of plagiarism. It is common for 
> programmers to rediscover algorithms that are basically simple, but very 
> good for some special cases -- and perhaps for just these reasons are 
> not very well known.
> 
> I could imagine posing this sorting problem (sorting a dense set of 
> numbers in a known, not too wide range) in a class on programming (not 
> an advanced class, either) and would expect some of the students to use 
> this method (i.e. Counting Sort) in their solutions.
> 
> > Update on performance.
> >
> > 42750 seven-digit positive integers were sorted in between 1 and 2 seconds.
> >
> > Waiting to hear regarding "Count Sort".
> 
> Since your method is an implementation of Counting Sort, you are 
> actually measuring "Counting Sort", at least in one implementation.
> 
> -- 
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
>        .      @       .

Thanks for that.

The very salient thing that everybody is missing is the way the data is collected and sorted simultaneously in "Parallel Sort" compared to Count Sort.  Parallel Sort is more a piece of computer science being implemeted in the Ada programming language.

Frankly I am not familiar with Count Sort in practise (being a comparison program puts it beyond the pale to me ) but can I ask you one question that will make my point more clearly.

If I asked you to demonstrate "Count Sort" being used to sort a specimen set of data how would you go about making the data available to the program.

Somewhere along the line you would have to prepare an external batch file for reading in or you would key in the data interactively - it has to be like that all the time with Count Sort - herein lies the difference - my program captures the data in parallel at the very origin ie as it is computed - no double handling => huge time and labour saving.

The counting part is trivial.  It is the capturing concept that is the important difference between what I am calling Parallel Sort and what anyone else may call Count Sort .  The counting is almost benign when the elements of data index their own addresses in an array in both cases.  

There is only a very tenuous connection in this fact however, plus that both sort programs eschew all comparisom methods and simply count the data according to magnitude as the means of sorting it. This common factor is not sufficient in itself however in my view to be grounds for any one to say that they are largely related versions of the same program.  They have only a very small amount in common. It is a huge leap from my parallel program to the count sort program in doing this - they have far too little in common to be lumped together like this.

I await your answer on how is the data introduced to a sort program that you  would use at home say.

Regards,

Austin.