Re: Sorting

 BBS: Inland Empire Archive
Date: 02-08-93 (17:23)             Number: 302
From: VICTOR YIU                   Refer#: NONE
  To: WAYNE VENABLES                Recvd: NO  
Subj: Re: Sorting                    Conf: (2) Quik_Bas

 >>> Regurgitating David Wang to Wayne Venables <<<

Here's the -fastest- sorting routine I have found (I didn't make it):

----------8<----------8<  Here it is...

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

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

----------8<----------8<  Hope it helps!

Victor

... Earth is 98% full.. Please delete anybody you can.
--- Blue Wave/RA v2.10 [NR]
 * Origin: Hard Disc Cafe / Houston Texas / (713) 589-2690 / (1:106/30.0)