High-Speed String Sort For Atari BASIC

Everett Hutchison

Inspired by a previous COMPUTE! utility for Atari, this routine sorts strings with the lightning speed of machine language, yet it can be added to any BASIC program.

A recent article in COMPUTE! illustrated how to add a machine language search routine to Atari BASIC (see "High-Speed String Search for Atari BASIC," February, 1986). Another handy utility is the high-speed string sort, which can organize strings in a database, mailing list program, and the like.

The high-speed sort routine presented here is written in relocatable machine language, which means it can be added to any BASIC program without fear of memory conflicts. And it's fast—up to 900 times faster than BASIC. In the worst case, for instance, a BASIC bubble sort routine might take as long as five hours to sort 1000 strings. This routine can do it in 20 seconds.

Atari BASIC does not allow string arrays, so this sort works a little differently from those intended for other BASICs. All of the strings to be sorted are stored in one giant string. This string can have any legal string name. The sorted strings are actually substrings of the larger string.

The program demonstrates how to use the sort routine from BASIC. It creates and sorts 100 strings. Before calling the routine, you must DIMension a string 256 characters in length (see BUFFERS in line 10). The sort routine uses this string as a buffer. You must also POKE the starting address of the string into locations 232–233 (line 100). Call the routine with the following statement:

SORT = USR (ADR(SORT$), L, A, B, C, D, E, F)

The call to the sort routine includes seven variables. Here's an explanation of the variables used in the example statement:

L	length of each record
A	address of the beginning of the array to sort
B	ending address of the last record; this can be calculated by taking the start address of the string and adding the number of records times the record length
C	starting address of the last record; this works out to B—L
D	address of the buffer string
E	start of the search field within a record (beginning at 0)
F	end of the search field within a record

For instance, say that each record contains a name in its first ten characters and an age in the last two, and both fields are padded out with spaces as needed. To sort the names alphabetically, you would set the start of the search field to 0 and the end of the search field to 9. To sort the ages numerically, you would set the start of the search field to 10 and the end of the search field to 11.

The demonstration program creates 100 random strings, each of which is ten characters long. After the strings have been created, they are displayed on the screen. Once this is done, the program waits for a keypress and then sorts the strings. The strings are displayed again when the sorting is complete.

High-Speed String Sort

For instructions on entering this listing, please refer to "COMPUTE!'s Guide to Typing In Programs" in this issue of COMPUTE!.

JA 10 DIM SORT$ (169), BUFFER$ (256)
CD 20 FOR I = 1 TO 169 : READ A : SORT$ (I, I) = CHR$ (A) : NEXT I
JA 30 NR = 100 : RECLEN = 10 : DIM T$ (RECLEN), MASTER$ (NR* 10)
E0 40 PRINT "(CLEAR)CREATING RANDOM STRINGS" : POKE 752,1
EA 50 FOR A = 1 TO NR : FOR B = 1 TO 10 : T$(B,B) = CHR$ (65 + RND (1) *25) : NEXT B : PRINT A; "{UP}"
OF 60 MASTER$ ((A-1) *10 + 1, A*10) = T$ : NEXT A
FJ 70 PRINT "{CLEAR}" : FOR A = 1 TO NR: PRINT MASTER$ ((A-1) *10 + 1,A*10) : NEXT A
LK 80 PRINT "{CLEAR}{DOWN} PRESS ANY KEY TO SORT":GOSUB 150 : PRINT "{DOWN} SORTING"
KI 90 L = RECLEN: A = ADR(MASTER$):B = A + NR*RECLEN:C = B-RECLEN:D = ADR(BUFFER$) :E = 0 : F = 9
PK 100 ADDR = 41 + ADR (SORT$) :HB YTE = INT(ADDR/256) : LBY TE = ADDR-256*HBYTE : POKE 232, LBYTE : POKE 233, HBYTE
AL 110 SORT = USR (ADR(SORT$), L, A, B, C, D, E, F)
CH 120 PRINT "{DOWN}DONE" : PRINT "{DOWN}PRESS ANY KEY TO SEE STRINGS":GOSUB 150
PO 130 FOR A = 1 TO NR : PRINT MASTER$ ((A-1) *10 + 1, A*10):NEXT A
MP 140 POKE 752,0 : END
CO 150 POKE 764, 255
MN 160 IF PEEK(764) = 255 THEN 160
HI 170 RETURN
FI 180 DATA 104, 104, 104, 133, 240, 104, 133, 242, 133, 244, 104, 133, 241, 133, 243, 104, 133, 246, 104, 133, 245, 104, 133, 248, 104, 133
PE 190 DATA 247, 104, 133, 250, 104, 133, 249, 104, 104, 133, 230, 104, 104, 133, 231
KG 200 DATA 165, 242, 133, 252, 165, 241, 133, 251
EM 210 DATA 24, 165, 241, 101, 240, 133, 241, 144, 2, 230, 242
FJ 220 DATA 165, 242, 197, 246, 208, 6, 165, 241, 197, 245, 240, 29, 164, 230, 177, 241
BO 230 DATA 209, 251, 240, 13, 176, 223, 165, 242, 133, 252, 165, 241, 133, 251, 24, 144, 212, 200, 196, 231, 240, 207, 24, 144, 229
GH 240 DATA 160, 0, 177, 251, 145, 249, 200, 196, 240, 208, 247, 160, 0, 177, 243, 145, 251, 200, 196, 240, 208, 247, 160, 0, 177, 249
OL 250 DATA 145, 243, 200, 196, 240, 208, 247
FH 260 DATA 24, 165, 243, 101, 240, 133, 243, 144, 2, 230, 244
MC 270 DATA 165, 244, 197, 248, 208, 7, 165, 243, 197, 247, 208, 1, 96, 165, 244, 133, 242, 165, 243, 133, 241, 108, 232, 0