Dilwyn Jones wrote:
> The second one is much faster than the first.
They both use O(n) stack space. The both have O(n*n) worst cases. They
both use the first element as the mean, so will have O(n*n) when the
data is initially sorted. I'd not use either.
> Timing checks I did on
> it some time ago show that Quicksort is good on mixed random data,
Not "is good", but it "is very frequently good".
>
> which is usually where other sort routines slow down.
Nope. True for some.
> Where the data
> is in pretty good sorted order already, other sort routines can be
> faster.
Yes, for some others.
> Quicksort is a reasonable choice as a general purpose sort
> routine where the data distributions and array sizes aren't really
> known in advance.
>
No. It is /not/.
> Mark Knight sent QL Today a listing some years ago of a sort called
> pigeon sort, which could be faster than Quicksort but it was much
> longer than these listings and I couldn't understand it at the time.
>
>
It's the one that you use in post offices. Pigeonholes. Highly
appropriate in /very/ specialised circumstances..
> Improvement suggestions for the above listings welcome.
>
>
I'm thinking about it... first I'm trying to build QLAY to run on
Ubuntu, just for fun. Or maybe I'll re-implement SuperBasic - as Mono-based.
In the short term, here's my C code for heapsort, hand edited to SB, and
utterly untested!
DEFine PROCedure pushroot
REPeat down
w=2*free+2:REMark save pointer and get right descendant
IF w>=count
IF w>count:EXIT down ELSE w=w-1:REMark single leaf
ELSE IF data(w-1)>data(w): w=w-1:REMark larger leaf
IF data(w)<=nxt:EXIT down:REMark got max-heap property
data(free)=data(w):REMark promote child and keep looking
free=w
END REPeat down
data(free)=nxt
END DEFine
DEFine PROCedure heapsort(data, count)
LOCal v,w,free,nxt:v=count/2
REPeat build
IF v<=0:EXIT build
v=v-1
nxt=data(v):free=v:pushroot
END REpeat build
REPeat extract
IF count<=0:EXIT extract
count=count-1
nxt=data(count):data(count)=data[0]:free=0:pushroot
END REPeat extract
END DEFine
_______________________________________________
QL-Users Mailing List
http://www.q-v-d.demon.co.uk/smsqe.htm
