Re: Recapping on “Bug Sort”.

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

On Saturday, June 23, 2012 9:12:59 PM UTC+1, Niklas Holsti wrote:
> On 12-06-23 22:07 , Austin Obyrne wrote:
> > 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.
> >
> > 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.
> 
> Yes, it is a neat feature of Counting Sort that the first step of the 
> sort -- adding the values to the "count" array -- can be done for each 
> new value separately, independently of the other values (since it is not 
> a comparison sort). Only the second step, the final scan of the "count" 
> array and output of the values in sorted order, must be delayed until 
> all values are present.
> 
> This means, as you say, that the program can do the first step (add to 
> "count" array) immediately when a new value is generated; it is not 
> necessary to first collect all the values in some list, say, and then 
> sort them.
> 
> But I don't think that the group is "missing" this fact; rather, we see 
> that it does not change the order of complexity (big-oh) of the 
> algorithm, so it is not very interesting.
> 
> In fact, I'm not at all sure that adding the new values to the "count" 
> array immediately is faster than first collecting them in a dense, 
> unordered structure (array or list) and then sorting them. The frequent 
> scattered references to the large "count" array can stress the data 
> cache and virtual memory system, perhaps causing more data-cache misses 
> and page faults which could make the program run slower.
> 
> > 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.
> 
> This is not an interesting question, again because the complexity of 
> writing out and reading in a list of N integers is linear, O(N), in the 
> number of integers.
> 
> > Somewhere along the line you would have to prepare an external batch
> > file for reading in or you would key in the data interactively
> 
> I can't make head or tail of that. You seem not to know how one can pass 
> data from one part of a program to another, or from one program to 
> another, without human intervention.
> 
> > 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.
> 
> My view is the opposite. The "capturing" is just normal programming, 
> passing data from here to there within a program. Adding the data to the 
> "count" array at once may or may not be an advantage for speed, see 
> above. From the point of view of the sorting problem, the central point 
> in Counting Sort is the "count" array that is indexed directly by the 
> values to be sorted. *When* then values are added to the array is not 
> imporant, IMO.
> 
> -- 
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
>        .      @       .

Many thanks for all the contributions.  I am drawing a line under this topic now. I gather from your last communique that Count Sort is also an embedded sort program identical to the use I envisaged for my Parallel Sort.  I had decided that this was generally not the case and Count Sort was used interactively only in say academia (with full respect to academia).  Apparently I was wrong there.

Many thanks again for your help in this entire matter.

Austin.