Re: Recapping on “Bug Sort”.

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

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
       .      @       .