Re: Sort Speed

 BBS: Inland Empire Archive
Date: 05-10-92 (09:18)             Number: 188
From: MIKE AVERY                   Refer#: NONE
  To: RICHARD VANNOY                Recvd: NO  
Subj: Re: Sort Speed                 Conf: (2) Quik_Bas

MA>>Quick            34,755           891              38
MA>>Radix             3,307           774               9
MA>>Shell            11,518         2,408              20

 RV> I was somewhat surprised that Shell beat Quick.  I presume
 RV> that with a large number of records, Quick might beat
 RV> Shell.

 RV> I've never seen Radix Sort code.  Is is short enough you
 RV> could post it here?

Quick has some pathological cases, and we may have hit one.  Or perhaps
the implementation left something to be desired (grin).  In particular,
the code I put in that adds the profiling and screen display can effect
some sorts more than others.

As to Radix, when I coded the test I was unsure about whether counting
comparisons was really correct.  You see, Radix sorts without comparing
data.  All it does is bit tests.  Like the Quick sort, it is a
partitioning sort.  It starts with the high order bit of the key, scans
from the bottom of the array upwards until it finds an element with the
bit clear (or reaches the start of the array), notes the location, starts
a scan from the top of the array looking for an element that has the bit
set, or until it reaches the marked location.  If the pointers are not the
same, the data elements are swapped, and the scan resumes.

Once the pointers meet, we know that all the elements above that point
have the bit under test clear, and all the elements below that point have
the bit under test set.  The subarrays are further tested.

The sort presupposes that the keys are the same length, and that the
numeric representation makes this test valid - floating point
representation might give odd results, as would varying length strings
unless they were padded.

The code is from Knuth and is largely undocumented and unstructured.  I
have been meaning to clean it up, but it works, so I have not done so.
That is one of the BIG reasons that I have not posted the sort demo
anywhere.  Hope it is of some use to you.  As with the last sort, I am
striping the profiling code out to simplify matters.  The first 6 or so
lines are setup code that I put in the main module, so the arrays would
not need to be set up each time the sort was called.  If I were
generalizing the sort, I would not hard code the key size and re-dim the
arrays as needed.

CONST BitMax% = 15   'Max # of bits in keys for Radix sort
DIM SHARED BitMaps!(BitMax%)

'build the BitMap! array
FOR I% = 1 TO BitMax%
    BitMaps!(I%) = 2 ^ (BitMax% - I%)
NEXT I%

SUB RadixSort (WorkSpace$, StartSort%, EndSort%)

' Do a sort using the Radix exchange.  It uses the fewest compares of ANY
' sort - none!  It is based on bit tests.  It is a partiting sort, similar
' to the Quick Sort.  Discussed in Knuth's "Sorting and Searching", pages
' 123-134.

'optimize the sucker to eliminate needless passes
MaxSort% = 0
FOR I% = StartSort% TO EndSort%
    IF Work%(I%) > MaxSort% THEN
       MaxSort% = Work%(I%)
    END IF
NEXT I%

BitUnderTest% = 1

DO WHILE BitMaps!(BitUnderTest%) > MaxSort%
   BitUnderTest% = BitUnderTest% + 1
LOOP

R1:
L% = StartSort%
R% = EndSort%

R2:
IF L% = R% THEN GOTO R10
I% = L%
J% = R%

R3:
IF (BitMaps!(BitUnderTest%) AND Work%(I%)) = BitMaps!(BitUnderTest%)
   THEN GOTO R6

R4:
I% = I% + 1
IF I% <= J% THEN GOTO R3
GOTO R8

R5:
IF (BitMaps!(BitUnderTest%) AND Work%(J% + 1)) = 0 THEN GOTO R7

R6:
J% = J% - 1
IF I% <= J% THEN GOTO R5
GOTO R8

R7:
CALL Swapper(I%, J% + 1)
GOTO R4

R8:
BitUnderTest% = BitUnderTest% + 1
IF BitUnderTest% > BitMax% THEN GOTO R10
IF J% < L% OR J% = R% THEN GOTO R2
IF J% = L% THEN L% = L% + 1: GOTO R2

R9:
StackPointer% = StackPointer% + 1
Stack%(StackPointer%, 0) = R%
Stack%(StackPointer%, 1) = BitUnderTest%
R% = J%
GOTO R2

R10:
IF StackPointer% = -1 THEN GOTO Rexit
L% = R% + 1
R% = Stack%(StackPointer%, 0)
BitUnderTest% = Stack%(StackPointer%, 1)
StackPointer% = StackPointer% - 1
GOTO R2

Rexit:
END SUB


Good luck,
Mike

--- via Silver Xpress V3.00
 * Origin: Silver Xpress Mail System (1:382/10@fidonet)