CLS
PRINT "  +------------------------------------------+  "
PRINT "  |                                          |  "
PRINT "  |               QUICKSORT                  |  "
PRINT "  |                                          |  "
PRINT "  |  This program sorts an array of strings  |  "
PRINT "  |    into alphabetical order, using the    |  "
PRINT "  |    well-known 'QuickSort' algorithm.     |  "
PRINT "  |                                          |  "
PRINT "  +------------------------------------------+  "'


// A collection of random words... (feel free to add more)

DATA one, two, three, fish, alphabet, elephant, zebra
DATA forwards, backwards, indigo, silicon, graphics
DATA apple, imagery, caterpillar, underneath, flow
DATA river, time, people, silver, thread, gold
DATA glasgow, york, carlisle, edinburgh, aberfeldy
DATA immune, sheep, cattle, abacus, computer, microchip
DATA virtual, machine, comal, better, than, basic
DATA xyzzy, plugh, plover, frotz, frobozz, lagach
DATA lengthy, predestination, attenuated, verbosity

// Count the words

i% := 0
WHILE NOT EOD DO
    i% := i% + 1
    READ foo$
ENDWHILE
RESTORE
num_words% := i%

// Copy the words into an array

DIM word$ (num_words%)
FOR i% := 1 TO num_words% DO
    READ word$ (i%)
NEXT i%

// Sort the array

PRINT "There are "; num_words%; " words to be sorted:"'
print_words (word$ (), 1, num_words%)

PRINT '"Sorting the words... "
start_time% := TIME
quicksort (word$ (), 1, num_words%)
PRINT "That took "; (TIME - start_time%) / 60; " seconds."'

PRINT "Here are the words in alphabetical order:"'
print_words (word$ (), 1, num_words%)


// ------------------------------------------------------
//  Procedures
// ------------------------------------------------------


PROC print_words (REF word$ (), from%, to%) CLOSED
    FOR i% := from% TO to% DO
        PRINT word$ (i%)
    NEXT i%
ENDPROC print_words

PROC swap_words (REF a$, REF b$) CLOSED
    c$ := a$
    a$ := b$
    b$ := c$
ENDPROC swap_words

PROC quicksort (REF word$ (), lhs%, rhs%) CLOSED
    IF lhs% < rhs% THEN
        lhs_scan% := lhs%
        rhs_scan% := rhs%
        pivot% := (lhs% + rhs%) / 2
        comp$ := word$ (pivot%)
        REPEAT
            WHILE word$ (lhs_scan%) < comp$ DO lhs_scan% := lhs_scan% + 1
            WHILE word$ (rhs_scan%) > comp$ DO rhs_scan% := rhs_scan% - 1
            IF lhs_scan% <= rhs_scan% THEN
                swap_words (word$ (lhs_scan%), word$ (rhs_scan%))
                lhs_scan% := lhs_scan% + 1
                rhs_scan% := rhs_scan% - 1
            ENDIF
        UNTIL lhs_scan% > rhs_scan%
        quicksort (word$ (), lhs%, rhs_scan%)
        quicksort (word$ (), lhs_scan%, rhs%)
    ENDIF
ENDPROC quicksort