CAPUTE!:
Modifications Or Corrections To Previous Articles

Further Notes on "Fast Sort For PET/CBM"

The following information from Jim Russo will aid in adapting the PET/CBM machine language sort utility to work within a BASIC program. "Fast Sort" appeared in COMPUTE!, May, 1982, #24, pg. 160:

This routine operates on strings of equal length which occupy contiguous memory locations. It does not know about variable names or arrays. The example given in the article uses Program 2 to collect some data, and then Program 3 to read it, in order, into a fresh string data space, without any extra string variables. Both functions could be done in the same program if the data was written into an array as it was collected, and then the following line was used to move the data into a contiguous area at the beginning of string memory:

FORI=0TOTN-1:   A$(I)=A$(I):NEXT

In a larger program with more than one array, this same technique could be used to move each array to the appropriate place when it was time for it to be sorted.

Line 150 in Program 3 will fail for certain values of length and number of records. A better way to write it is:

150  AA=256*HA + LA + LN + 2 : POKE179, AA AND 255:POKE180,AA/256

The two extra bytes used in each string by BASIC 4.0 are a pointer back to the variable data area, where the string length and starting address are stored. After a sort, these pointers are not valid. No harm will be done as long as none of the sorted strings is redefined by the program. If some of the sorted strings are redefined by the program, then a subsequent garbage collection will cause chaos. To illustrate this, try adding the following line to Program 3:

175  A$(1)="NEW STRING #1":X=FRE(0)

If there is enough room for two copies of the array data in string memory, then the following two lines will fix the problem:

125 IF FRE(0) < 270 + TN*(LN + 2)THENPRINT"NO ROOM":STOP
175 FORI= 0 TO TN-1: A$(I)=A$(I): NEXT

Line 125 forces a garbage collection, and makes sure there will be enough room for line 175 to execute without causing another garbage collection. Line 175 fixes the pointers by rewriting all of the sorted strings.