Apple Fast Sort

John Sarver

It can take a long time to put a list into alphabetical order. In a recent experiment, using a basic bubble sort routine, it took the author's Apple eight hours and 57 minutes to sort 1000 randomly created strings of random length between one and 20 characters. This subroutine puts both one- and two-dimensional Apple arrays in order at a tolerable speed: that same list of 1000 strings now takes one minute and 45 seconds.

Strings values, when assigned, are stored at the very top of Apple's free RAM, and as more strings are assigned, they are stored below the strings already in memory. A table, created when you use the DIM statement, keeps track of where each string is in RAM.

Some important information is stored at the beginning of this table. The first byte represents the first character in the variable name. The second byte represents the second character in the variable name plus $80 (adding $80 designates it as a string array rather than an integer or decimal point number array). The next pair of bytes gives the length of this pointer table.

The fifth byte is the number of dimensions that you have used with the DIM statement. If you used a two-dimensional array, the next two bytes tell how many variables are in the second part of the dimension (if three-dimensional, the next four bytes, and so on).

The final two bytes of information are the number of strings in the first dimension. The table begins here. Each variable is located by a three-byte pointer. The first byte is the length of the record, and the next two point to where the first character of the variable is stored. These pointers are always in order from the zero dimension to the nth dimension.

At the end of this grouping of pointers are the pointers for the first group of the second dimensioned part of the array. Following this is the second group of pointers for the second dimensioned part of the array, and so on. If you used a one-dimensional array, there is only one group of pointers.

As you can see, there is no need to sort the strings themselves. Just sort the pointers. Therefore, there is no time wasted in garbage collection and, in most cases, the length of the strings does not affect the time of execution.

Simple To Use

Using this sort is quite simple. Apple stores the last variable used in $81 and $82, so you may need to insert a statement in your BASIC program such as A$(0) = A$(0) (see line 90 of Program 2), or you may POKE these values in if you are putting this utility on another machine. The sort can be easily changed to use the zero dimension of an array if you wish. To do this, simply change the following lines in the BASIC loader (Program 1).

120 IF CK  < > 56854 THEN PRINT "CHECK DAT
       A  STATEMENTS FOR ERROR": STOP
200 DATA 169,0,133,253,133,239,169,1
400 DATA 165,6,105,2,133,6,169,0

If you are using a two-dimensional array, you will need to store the records that are to be put in order by using the zero subscript of the second dimension (that is, A$(l,0), A$(2,0), etc.). The accompanying arrays (A$(l,l), A$(2,l), A$(l,2), A$(2,2), etc.) will be kept with their respective zero-subscripted record.

The sort will automatically ascertain if you are using a one- or two-dimensional array and will adjust itself accordingly. You may use any number of subscripts desired in one-dimensional arrays and in the first part of the two-dimensional arrays. But don't try to use anything larger than a two-dimensional array, or attempt to use more than 255 variables in the second part of your two-dimensional array. Some of the corresponding subarrays would not be properly aligned.

Program 1 loads the machine language sorting routine into RAM. You should save this on disk by typing:

BSAVE SORT, A$944A,L$1B6

Program 2 provides an example of the steps necessary to use the routine.