Quicksort code

 BBS: Inland Empire Archive
Date: 02-24-94 (09:01)             Number: 191
From: BRIAN MCLAUGHLIN             Refer#: NONE
  To: JEFF COCHRAN                  Recvd: NO  
Subj: Quicksort code                 Conf: (2) Quik_Bas

Here's Cornel Huth's excellent code for a quicksort (slightly
rejiggered by me). You mentioned updating the screen within the sorting
loop as a possible source of slowdown...and you may be on to something
there. (A screen update every few seconds should be enough for anyone.)

If this code doesn't deliver the snap and speed you want, you may need
to rethink your whole approach -- maybe use some kind of hashing or
indexing on the fly. I am not a database expert and can't help much
there.

'----------------------- START CODE ----------------------------

DECLARE SUB QuickSort (Lower%, Upper%, Array$())

TYPE QSortStackType  'for QuickSort
   Low AS INTEGER
   Hi AS INTEGER
END TYPE


'=========================================
 SUB QuickSort (Lower%, Upper%, Array$())
'=========================================
  'QuickSort (iterative rather than recursive).
  'Public domain code, by Cornel Huth. (Slightly revamped.)

  'Lower% and Upper% bound the area to be sorted within Array$.
  'To change the array type, change the array specifier in every
  'instance of "Array$" and change the variable "Compare$", too.

  'To discover just how much of the "stack" array has been used,
  'unREM the lines containing references to MaxStackPtr%

  DIM LStack(1 TO 128) AS QSortStackType 'our "stack" array
  StackPtr% = 1                          'our "stack" pointer

  'MaxStackPtr% = StackPtr%
  LStack(StackPtr%).Low = Lower%
  LStack(StackPtr%).Hi = Upper%
  StackPtr% = StackPtr% + 1              'offset the subtraction, below

  DO
    StackPtr% = StackPtr% - 1
    Low% = LStack(StackPtr%).Low
    Hi% = LStack(StackPtr%).Hi

    DO
      Border1% = Low%
      Border2% = Hi%
      Mid% = (Low% + Hi%) \ 2
      Compare$ = Array$(Mid%)
      DO
        DO WHILE Array$(Border1%) < Compare$
          Border1% = Border1% + 1
        LOOP

        DO WHILE Array$(Border2%) > Compare$
          Border2% = Border2% - 1
        LOOP

        IF Border1% <= Border2% THEN
          SWAP Array$(Border1%), Array$(Border2%)
          Border1% = Border1% + 1
          Border2% = Border2% - 1
        END IF

      LOOP WHILE Border1% <= Border2%

      IF Border2% - Low% < Hi% - Border1% THEN
        IF Border1% < Hi% THEN
          LStack(StackPtr%).Low = Border1%
          LStack(StackPtr%).Hi = Hi%
          StackPtr% = StackPtr% + 1
        END IF
        Hi% = Border2%
      ELSE
        IF Low% < Border2% THEN
          LStack(StackPtr%).Low = Low%
          LStack(StackPtr%).Hi = Border2%
          StackPtr% = StackPtr% + 1
        END IF
        Low% = Border1%
      END IF

    'Perhaps do your screen updates here?

    LOOP WHILE Low% < Hi%
    'IF StackPtr% > MaxStackPtr% THEN MaxStackPtr% = StackPtr%

  LOOP WHILE StackPtr% <> 1

  'PRINT "MAX StackPtr%"; MaxStackPtr%

END SUB

'-------------------------- END CODE ---------------------------

 * SLMR 2.1a * Dyslexics of the world, untie!
$$62
--- GEcho 1.00+
 * Origin: The Disk Box ][ Node 3 (313)790-6828 ZOOM 14.4K (1:2202/11)