home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / QBAS / PBCLON20.ZIP / PBC$BAS.ZIP / PSORTST.BAS < prev    next >
BASIC Source File  |  1992-10-07  |  2KB  |  78 lines
  1. '   +----------------------------------------------------------------------+
  2. '   |                                                                      |
  3. '   |        PBClone  Copyright (c) 1990-1992  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 PSortSt (Ptr%(), Array() AS STRING, Elements%, CapsCount%)
  16.    DIM S(0 TO 16) AS STRING
  17.    DIM x AS STRING
  18.    DIM SortStack(1 TO 16) AS Partition
  19.    S% = 1
  20.    SortStack(1).Lft = 1
  21.    SortStack(1).Rht = Elements%
  22.    DO
  23.       L% = SortStack(S).Lft
  24.       R% = SortStack(S).Rht
  25.       S% = S% - 1
  26.       DO
  27.          i% = L%
  28.          j% = R%
  29.          IF CapsCount% THEN
  30.             x = Array(Ptr%((L% + R%) \ 2))
  31.             DO
  32.                WHILE Array(Ptr%(i%)) < x
  33.                   i% = i% + 1
  34.                WEND
  35.                WHILE x < Array(Ptr%(j%))
  36.                   j% = j% - 1
  37.                WEND
  38.                IF i% <= j% THEN
  39.                   SWAP Ptr%(i%), Ptr%(j%)
  40.                   i% = i% + 1
  41.                   j% = j% - 1
  42.                END IF
  43.             LOOP UNTIL i% > j%
  44.          ELSE
  45.             x = UCASE$(Array((L% + R%) \ 2))
  46.             DO
  47.                WHILE UCASE$(Array(Ptr%(i%))) < x
  48.                   i% = i% + 1
  49.                WEND
  50.                WHILE x < UCASE$(Array(Ptr%(j%)))
  51.                   j% = j% - 1
  52.                WEND
  53.                IF i% <= j% THEN
  54.                   SWAP Ptr%(i%), Ptr%(j%)
  55.                   i% = i% + 1
  56.                   j% = j% - 1
  57.                END IF
  58.             LOOP UNTIL i% > j%
  59.          END IF
  60.          IF j% - L% < R% - i% THEN
  61.             IF i% < R% THEN
  62.                S% = S% + 1
  63.                SortStack(S%).Lft = i%
  64.                SortStack(S%).Rht = R%
  65.             END IF
  66.             R% = j%
  67.          ELSE
  68.             IF L% < j% THEN
  69.                S% = S% + 1
  70.                SortStack(S%).Lft = L%
  71.                SortStack(S%).Rht = j%
  72.             END IF
  73.             L% = i%
  74.          END IF
  75.       LOOP UNTIL L% >= R%
  76.    LOOP WHILE S%
  77. END SUB
  78.