home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 13 / CD_ASCQ_13_0494.iso / maj / 419 / psorti.bas < prev    next >
BASIC Source File  |  1994-03-13  |  2KB  |  60 lines
  1. '   +----------------------------------------------------------------------+
  2. '   |                                                                      |
  3. '   |        PBClone  Copyright (c) 1990-1994  Thomas G. Hanlin III        |
  4. '   |                                                                      |
  5. '   +----------------------------------------------------------------------+
  6.  
  7. ' QuickSort derived from "partition sort" algorithm given in
  8. ' "Algorithms & Data Structures" by Niklaus Wirth, 1986
  9.  
  10.    TYPE Partition
  11.       Lft AS INTEGER
  12.       Rht AS INTEGER
  13.    END TYPE
  14.  
  15. SUB PSortI (Ptr%(), Array() AS INTEGER, Elements%)
  16.    DIM x AS INTEGER
  17.    DIM SortStack(1 TO 16) AS Partition
  18.    S% = 1
  19.    SortStack(1).Lft = 1
  20.    SortStack(1).Rht = Elements%
  21.    DO
  22.       L% = SortStack(S).Lft
  23.       R% = SortStack(S).Rht
  24.       S% = S% - 1
  25.       DO
  26.          i% = L%
  27.          j% = R%
  28.          x = Array(Ptr%((L% + R%) \ 2))
  29.          DO
  30.             WHILE Array(Ptr%(i%)) < x
  31.                i% = i% + 1
  32.             WEND
  33.             WHILE x < Array(Ptr%(j%))
  34.                j% = j% - 1
  35.             WEND
  36.             IF i% <= j% THEN
  37.                SWAP Ptr%(i%), Ptr%(j%)
  38.                i% = i% + 1
  39.                j% = j% - 1
  40.             END IF
  41.          LOOP UNTIL i% > j%
  42.          IF j% - L% < R% - i% THEN
  43.             IF i% < R% THEN
  44.                S% = S% + 1
  45.                SortStack(S%).Lft = i%
  46.                SortStack(S%).Rht = R%
  47.             END IF
  48.             R% = j%
  49.          ELSE
  50.             IF L% < j% THEN
  51.                S% = S% + 1
  52.                SortStack(S%).Lft = L%
  53.                SortStack(S%).Rht = j%
  54.             END IF
  55.             L% = i%
  56.          END IF
  57.       LOOP UNTIL L% >= R%
  58.    LOOP WHILE S%
  59. END SUB
  60.