Modified Shell Sort

 BBS: Inland Empire Archive
Date: 05-27-92 (01:46)             Number: 133
From: RICH GELDREICH               Refer#: NONE
  To: ALL                           Recvd: NO  
Subj: Modified Shell Sort            Conf: (2) Quik_Bas

    A couple of months ago, I gave a friend of mine, Dave Cooper,
some QB source code for a simple shell sort. He made an assembly version
of it, and to make a short story shorter, he wasn't satisfied with the
speed...

    Well, since Dave is one of the high speed graphics freaks, he
just had to make it faster. Well- he did. Here it is.

    The question is, what is this sort called? It's not a shell sort
any more, that's for sure. Does this sort actually exist? I've never
seen it before...

-----------Rip Here-----------

'Fast modified shell sort implemented by Rich Geldreich.
'Sort algorithm by Dave Cooper.
'May, 1992
'For QB4.5
DEFINT A-Z
CONST True = -1, False = NOT True
DIM A(1000), Pointers(1000)
FOR A = 0 TO 1000
    A(A) = RND * 500
    Pointers(A) = A
NEXT
A! = TIMER
Low = 0
High = 1000
Mid = (Low + High) \ 2
DO
    FOR A = Low TO High - Mid
        IF A(Pointers(A)) > A(Pointers(A + Mid)) THEN
            SWAP Pointers(A), Pointers(A + Mid)
            CompareLow=A - Mid
            CompareHigh=A
            DO WHILE CompareLow>=Low
                IF A(Pointers(CompareLow))>A(Pointers(CompareHigh)) THEN
                    SWAP Pointers(CompareLow),Pointers(CompareHigh)
                    CompareHigh = CompareLow
                    CompareLow = CompareLow-Mid
                ELSE
                    EXIT DO
                END IF
            LOOP
        END IF
    NEXT
    Mid = Mid \ 2
LOOP WHILE Mid > 0
B! = TIMER
CLS
FOR A = 0 TO 1000
    PRINT A(Pointers(A));
NEXT
PRINT : PRINT "sort time ÷"; B! - A!; "seconds"


    This sort is very fast, and easy to implement. Run it compiled... I
could of made this implementation faster by eliminating all of those
pointers, but I think it's better that way...

    Rich Geldreich

--- RBBSMAIL 17.2A
 * Origin: Computer Co-Op RBBS HST, 609-784-9404 Voorhees
NJ (RBBS-PC 1:266/29)