I wrote:
<>
Ooops! A couple of typos:
<>
> rem Random data
<>
> FOR i% = 1 TO 60
> MATEQU b% TO a%: QUICKSORT a%; 1
> END FOR i%
<>
should have been:
FOR i% = 1 TO 60
MATEQU b% TO a%: QUICKSORT b%; 1
END FOR i%
which gives:
same sorted (dt) rnd
9 6 0 10 (n = 10k)
21 12 0 21 (n = 20k)
32 18 0 33 (n = 30k)
Im no mathematician , but doesnt this show that with pre-sorted data the
speed is proportional to n, and for random data, timings are pretty much
consistent with n*ln(n)? These are wierd characteristics as, traditionally,
quicksort implementations sort pre-sorted data in n*n/2 time...
Per
_______________________________________________
QL-Users Mailing List
http://www.q-v-d.demon.co.uk/smsqe.htm
