[futurebasic] Re: Sorting Hummms...

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : November 1997 : Group Archive : Group : All Groups

From: Joe Kovac <locality@...>
Date: Wed, 12 Nov 1997 12:15:44 -0400
A while ago I had to write code to figure out the actual pointers to an
index. I forget why, it was pretty long ago... but anyway I thought that it
might make a substantial improvement to the speed of sorting if you didn't
make INDEX step through the entire array each time. You also get the memory
benefits of the variable sized strings. I think that Indexes are managed
with handles, so you'll probably have to call the fn that recalculates the
pointers each time, but it goes pretty quick. (just think that one use of
INDEX$ in your sort routine would have performed nearly the equivilant of
this each time it was called... and it got called twice.) gIndexNums&, when
done, holds the sorted index numbers. gIndexPtrs& holds the sorted index
pointers, but that's less consequential. It executes in 4 ticks on my
PowerMac 8600/200 without using QuickSort... although I have that around
here somewhere too if you want it.

By the way: To the person who questioned what one of my previous messages
had to do with FB... (I lost some recent messages) Well, nothing really,
I'm sorry. Sometimes I forget this list is about FutureBASIC. I hope I'm
not seen as chronic X-FB'er. (considering how often I post, probably not...)

Well, here's the complete code: (it's pretty short: just 4 fns.)

DIM gIndexNums& (2000)
DIM gIndexPtrs& (2000)
DIM gTotalEntries&

END GLOBALS

LOCAL FN InitMain
  CLEAR 20000
  FOR A= 0 TO 2000
    FOR B = 0 TO 3
      INDEX$(A) = INDEX$(A)+CHR$(RND(25)+65)
    NEXT B
  NEXT A
  gTotalEntries& = 2000
END FN

LOCAL FN InitArrays
  MemAddr& = MEM (_indxAddr)
  FOR A = 0 TO gTotalEntries&
    gIndexNums& (A) = A
    gIndexPtrs& (A) = MemAddr&
    MemAddr& = MemAddr& + 1 + PEEK (MemAddr&)
  NEXT A
END FN

LOCAL FN PrintPtrs
  FOR A=0 TO 15
    Ptr& = gIndexPtrs& (A)
    PRINT Ptr&.nil$,
  NEXT A
END FN

LOCAL FN SortIndex
  DIM Gap,Switch,Count,TestElem,TotalItems
  TotalItems=gTotalEntries&-1

  Gap = TotalItems
  DO
    Gap=Gap/1.3
    IF Gap < 1 THEN Gap = 1
    Switch = _False
    FOR Count = 0 TO TotalItems - Gap
      TestElem = Count + Gap

      TestPtr& = gIndexPtrs& (TestElem)
      CompPtr& = gIndexPtrs& (Count)

      LONG IF CompPtr&.nil$>TestPtr&.nil$
        SWAP gIndexNums& (Count), gIndexNums& (TestElem)
        SWAP gIndexPtrs& (Count), gIndexPtrs& (TestElem)
        INC (Switch)
      END IF
    NEXT Count
  UNTIL Switch = _False AND Gap = 1
END FN

WINDOW #1
FN InitMain

PRINT "GO!"
PRINT

StartTicks& = FN TICKCOUNT
FN InitArrays
InitTicks& = FN TICKCOUNT
FN SortIndex
SortTicks& = FN TICKCOUNT
FN PrintPtrs

PRINT "Ticks to setup: ";InitTicks& - StartTicks&
PRINT "Ticks to sort:  ";SortTicks& - InitTicks&
PRINT "Total Ticks:    ";SortTicks& - InitTicks&

DO
UNTIL FN BUTTON


Joe K.
locality@...