BBS: Inland Empire Archive
Date: 10-24-92 (07:14) Number: 373
From: JERRY ALDRICH Refer#: NONE
To: RYAN WELLMAN Recvd: NO
Subj: Re: Fast Sorting Algorith Conf: (2) Quik_Bas
(* On or about 22 Oct 92 14:36:00, in a message to All, *)
(* Ryan Wellman blurted out the following: *)
RW> Hello,
RW> This is a sort routine that I just wrote. It is extremely fast.
RW> It will sort an array with 16,383 random entries in 7.5 seconds on a
RW> 386/40. I would like to see your comments/modifications, and I would
RW> like to see if this routine is currently the fastest one in existance.
RW> I warn you, if it is I'll be gloating. It's also fully comented so that
RW> you won't have many problemes figuring out what I'm doing.
Well, I though I had you beat :) The test I ran was on a 386SX/16 using
PDS 7.1 and the QBX environment. The only modification I made to your
routine was to strip out the comment lines. Here are the results when
running in the environment:
FastSort: .0585 MySort: .0605 based on 64 entries.
FastSort: .1699 MySort: .2207 based on 128 entries.
FastSort: .5996 MySort: .5507 based on 256 entries.
FastSort: 1.269 MySort: 1.208 based on 512 entries.
FastSort: 3.900 MySort: 3.679 based on 1024 entries.
FastSort: 8.679 MySort: 8.191 based on 2048 entries.
FastSort: 21.58 MySort: 20.11 based on 4096 entries.
FastSort: 74.31 MySort: 67.83 based on 8192 entries.
FastSort: 168.4 MySort: 153.4 based on 16384 entries.
At this point, I was pretty pleased with myself. However, just for
fairness, I decided to compile the thing and try it again. Here are the
results when compiled:
FastSort: 00000 MySort: 00000 based on 64 entries.
FastSort: .0488 MySort: .0605 based on 128 entries.
FastSort: .0605 MySort: .0507 based on 256 entries.
FastSort: .1093 MySort: .1699 based on 512 entries.
FastSort: .4902 MySort: .6093 based on 1024 entries.
FastSort: 1.160 MySort: 1.259 based on 2048 entries.
FastSort: 2.800 MySort: 3.240 based on 4096 entries.
FastSort: 9.781 MySort: 11.15 based on 8192 entries.
FastSort: 22.12 MySort: 25.32 based on 16384 entries.
It a WHOPPING improvement for both routines in speed, but that's to be
expected. Much to my dismay, your routine was faster <Sigh>.
Now, explain why there is a difference! Here's the routine I used:
DEFINT A-Z
SUB MySort (InArray() AS INTEGER, Lower AS INTEGER, Upper AS INTEGER)
Span = Upper \ 2
DO WHILE (Span > 0)
FOR I = Span TO Upper - 1
FOR j = (I - Span + 1) TO 1 STEP -Span
IF InArray(j) <= InArray(j + Span) THEN EXIT FOR
SWAP InArray(j), InArray(j + Span)
NEXT j
NEXT I
Span = Span \ 2
LOOP
END SUB
Although yours seems to be faster, my simpler and smaller :)
Later!
Jerry
--- Renegade v8-27 Beta
* Origin: The Bumpkinland BBS - "Home of BLand Software" (1:296/3)
