Re: Sorting data points

["Eric G. Miller" <egm2@jps.net>]

On Sun, May 05, 2002 at 08:57:51PM +0200, DSC Siltec wrote:
> If I think about it, this definitely isn't the quicksort.  However, it 
> may be that it is mathematically equivalent to the heapsort.  In fact,
> it may be an easy implementation of the heap sort.  
> 
> Anyhow, when I was looking back at the data, the same Nlog2N factor came 
> out, and www.nr.com at least claims that they actually get that in their
> worst case.  In which case, they may be mathematically equivalent.  
> 
> The two methods are, at least, conceptually equivalent in terms of the
> general method.
> 
>   So if you wanted to use a standard algorithm, I guess I'd advocate the
> heapsort.
> 
>   But it's not quite the same as the one I described.

In an approximate way, you've described a merge sort which is generally
the preferred method of sorting linked lists and runs in N Log N 
consistently.  The main difference from your description is that the
list is recursively divided in half and then merged back together in
sorted order.  When all the recursion returns you perform the final
merge and then have a sorted list.  For a linked list, it doesn't
require any extra space, which is nice.

For arrays, quicksort is likely to do as well, and possibly better.  But
for 50 items, you could use a bubble sort or insertion sort and not
notice a performance hit.

-- 
Eric G. Miller <egm2@jps.net>


-- 
To UNSUBSCRIBE, email to debian-user-request@lists.debian.org 
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org