Quik_Bas Faq2.1 3/

 BBS: Inland Empire Archive
Date: 03-28-93 (21:04)             Number: 246
From: QUINN TYLER JACKSON          Refer#: NONE
  To: ALL                           Recvd: NO  
Subj: Quik_Bas Faq2.1       3/       Conf: (2) Quik_Bas

>>> Continued from previous message
        But, if you want ALL the variables to be STATIC, use the following
        method:

        SUB FooSub () STATIC
        :
        :
        :
        END SUB

        There are certain speed advantages to STATIC SUBs and FUNCTIONs,
        since variables are not created on the stack, but that is a more
        advanced issue.

        So, in summary:

        1.  SHARED allows SUBs and FUNCTIONs to use modular variables,
        2.  COMMON allows modules to share variables between themselves,
        3.  STATIC allows variables to retain their value between
            calls to the SUB or FUNCTION in question.

Q2.0    Commonly Requested Routines:

Q2.4    Okay, I've looked the whole thing over, Quinn, and I've realized
        something: the recursive QuickSortXXX routine eats the stack up
        pretty fast.  Is there another way?  Is there a way to implement
        a QuickSort SUB without using recursion?

A2.4    Yes, indeed there is.  Cornel Huth implemented an iterative
        quicksort algorithm, which I then tweaked a bit.  It is actually
        a bit faster than the other, and doesn't use too much of the stack.
        It accomplishes this by using an array to simulate a stack.  The
        modified version follows:

S2.0    HUTHSORT.BAS [P210S02.BAS]

' HUTHSORT.BAS written by Cornel Huth
' Iterative QuickSort Routine
'
' Tweaked by Quinn Tyler Jackson

SUB subHuthSortSTR (Array() AS STRING)
'               ^  TWEAK THESE    ^
'               | FOR OTHER TYPES |
'               `--+--------------'
'                  V
  DIM compare AS STRING

TYPE StackType
  low AS INTEGER
  hi AS INTEGER
END TYPE

DIM aStack(1 TO 128) AS StackType

  StackPtr = 1
  aStack(StackPtr).low = LBOUND(Array)
  aStack(StackPtr).hi = UBOUND(Array)
  StackPtr = StackPtr + 1

  DO
    StackPtr = StackPtr - 1
    low = aStack(StackPtr).low
    hi = aStack(StackPtr).hi
    DO
      i = low
      j = hi
      mid = (low + hi) \ 2
      compare = Array(mid)
      DO
        DO WHILE Array(i) < compare
          i = i + 1
        LOOP
    DO WHILE Array(j) > compare
          j = j - 1
        LOOP
        IF i <= j THEN
          SWAP Array(i), Array(j)
          i = i + 1
          j = j - 1
        END IF
      LOOP WHILE i <= j
      IF j - low < hi - i THEN
        IF i < hi THEN
          aStack(StackPtr).low = i
          aStack(StackPtr).hi = hi
          StackPtr = StackPtr + 1
        END IF
        hi = j
      ELSE
        IF low < j THEN
          aStack(StackPtr).low = low
          aStack(StackPtr).hi = j
          StackPtr = StackPtr + 1
        END IF
        low = i
      END IF
    LOOP WHILE low < hi
    'IF StackPtr > maxsp THEN maxsp = StackPtr
  LOOP WHILE StackPtr <> 1
END SUB

=======>8 SAMPLE 2.0 ENDS HERE 8<=========

Q2.5    Now that I've got so many neat ways to sort a list, I'd sure like
        to be able to locate an entry in it quickly.  I hear that a binary
        search is fast, but I just can't figure out how to do that.  How
        do I do a binary search?

A2.5    Binary searches are the fastest overall search method for standard
        sorted lists.  Such lists can be divided in two, looked at, and
        divided again as necessary.  A good search method is demonstrated
        here:

S3.0    BISEARCH.BAS [F210S03.BAS]


DEFINT A-Z
FUNCTION BiSearchSTR (Find AS STRING, Array() AS STRING)

Min = LBOUND(Array)             'start at first element
Max = UBOUND(Array)             'consider through last

DO
  Try = (Max + Min) \ 2         'start testing in middle

  IF Array(Try) = Find THEN     'found it!
    BiSearch = Try              'return matching element
    EXIT DO                     'all done
  END IF

  IF Array(Try) > Find THEN     'too high, cut in half
    Max = Try - 1
  ELSE
    Min = Try + 1               'too low, cut other way
  END IF
LOOP WHILE Max >= Min

END FUNCTION

=======>8 SAMPLE 3.0 ENDS HERE 8<=========

Q3.0    Advanced Topics -- "Hashing in QuickBASIC"
>>> Continued to next message

 * OLX 2.1 TD * Post all questions in this box --> []

--- Maximus 2.01wb
 * Origin: VKUG/VPCC QuickBasic Echo - Richmond, BC (1:153/151)