Re: Recapping on “Bug Sort”.

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

On 12-06-23 17:21 , Austin Obyrne wrote:
> On Saturday, June 23, 2012 2:08:58 PM UTC+1, Austin Obyrne wrote:
>> On Saturday, June 23, 2012 11:20:10 AM UTC+1, 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.
 > ...
>
> Final update on performance.
>
> These are the results:
>
> 14250 seven-digit positive integers 1 - 2 secs
>
> 28500 "" "" "" "" 1 - 2 secs
>
> 42750 "" "" "" "" 1 - 2 secs
>
> 85500 "" "" "" "" 2 - 3 secs
>
> Austin O'Byrne.
> Clearly, these are extraordinary times for a sort program.
> (the measuring method isn't sensitive enough to give more exact times.)

The times are not so good. I ran the following command on my MacBook Air 
(old model, not a superfast machine); this command generates a text file 
with 85500 7-digit numbers in a more or less mixed order and sorts it 
into descdending order with the Unix "sort" program:

yes | head -85500 | pr -n:7 -t | cut -d: -f1 | tr ' 0123456789' 
'09472601583' | (time sort -n -r >sorted)

The output from the "time" command that measures the "sort" process is:

real	0m0.133s
user	0m0.068s
sys	0m0.011s

This means that even the elapsed time, including all the I/O, is only 
0.133 seconds. Note that the "sort" program is a very general one, so it 
should have lots of overhead compared to a program written to sort only 
a set of integers.

If your program handles 7-digit integers, your "count" array will have 
10 million elements. Most of the time taken by your program will be 
spent in initializing the array to "all zero" and in scanning the array 
from start to end to pick up and output the 85500 numbers, which fill 
less than 1% of the array. This is the drawback of the Counting Sort 
method: if the data is sparse in its range, there is lots of overhead 
both in time and memory usage.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .