Re: Help!! (for someone e

 BBS: Inland Empire Archive
Date: 03-04-93 (16:29)             Number: 313
From: VICTOR YIU                   Refer#: NONE
  To: CASEY PEARSON                 Recvd: NO  
Subj: Re: Help!! (for someone e      Conf: (2) Quik_Bas

 >>> Regurgitating CASEY PEARSON to ALL <<<

 CP> am trying to implement the Quick Sort algorithm so I can test out how

Here's the fastest QuickSort I have seen (non-recursive).  It has already
been posted in this echo several times in the past 6 months....

-----------------snip here
DEFINT A-Z

DECLARE SUB Quicksort2 (sortarray%(), lower%, Upper%)
DECLARE FUNCTION RandInt% (lower%, Upper%)

TYPE stacktype 'for QuickSort2
  Low AS INTEGER
  hi AS INTEGER
END TYPE

COMMON SHARED Temp() AS INTEGER

'Quicksort2 Temp(), 1, count

SUB Quicksort2 (sortarray(), lower%, Upper%)

  'QuickSort iterative (rather than recursive) by Cornel Huth
  DIM lstack(1 TO 128) AS stacktype 'our stack
  DIM sp AS INTEGER 'out stack pointer
  sp = 1
  'maxsp = sp
  lstack(sp).Low = lower%
  lstack(sp).hi = Upper%
  sp = sp + 1
  DO
    sp = sp - 1
    Low = lstack(sp).Low
    hi = lstack(sp).hi
    DO
      I = Low
      J = hi
      mid = (Low + hi) \ 2
      compare = sortarray(mid)
      DO
        DO WHILE sortarray(I) < compare
          I = I + 1
        LOOP
        DO WHILE sortarray(J) > compare
          J = J - 1
        LOOP
        IF I <= J THEN
          SWAP sortarray(I), sortarray(J)
          I = I + 1
          J = J - 1
        END IF
      LOOP WHILE I <= J
      IF J - Low < hi - I THEN
        IF I < hi THEN
          lstack(sp).Low = I
          lstack(sp).hi = hi
          sp = sp + 1
        END IF
        hi = J
      ELSE
        IF Low < J THEN
          lstack(sp).Low = Low
          lstack(sp).hi = J
          sp = sp + 1
        END IF
        Low = I
      END IF
    LOOP WHILE Low < hi
    'IF sp > maxsp THEN maxsp = sp
  LOOP WHILE sp <> 1
  'PRINT "MAX SP"; maxsp
END SUB

FUNCTION RandInt% (lower, Upper) STATIC

   RandInt% = INT(RND * (Upper - lower + 1)) + lower

END FUNCTION
------------------ end

Victor

... Rhesus Pieces: Monkey in a blender.
--- Blue Wave/RA v2.10 [NR]
 * Origin: Hard Disc Cafe / Houston Texas / (713) 589-2690 / (1:106/30.0)