Sorting and Searching in Atari BASIC

Atari text screen listing jiffy timings for bubble, insertion and Shell sorts of 100 numbers, on random and on already sorted input

Sooner or later every program that keeps a list wants it in order: a high-score table, an address book, an inventory. Atari BASIC has no SORT command, so you write one. This guide gives three sort routines as drop-in subroutines, measures them against each other, and then tackles the problem specific to Atari BASIC: sorting names, when the language has no string arrays. It ends with binary search, the payoff for keeping data sorted.

What you'll learn: how bubble, insertion and Shell sorts work and how fast each is in BASIC, how to sort fixed-length records held in one string by sorting an index array, how string comparison orders things, and how to find an item in a sorted list in a handful of steps.

What you need: Atari BASIC on any Atari 8-bit machine or emulator. The fixed-length string technique is introduced in Atari BASIC String Handling and Tricks, and the timing method in Making Atari BASIC Faster; this guide builds on both.

1. A test bench

To compare sorts fairly, fill an array with random numbers once, copy it before each run and time the run with the jiffy clock (locations 18–20). Lines 800–900 below are the bench; the three sorts follow as subroutines at 1000, 2000 and 3000.

10 N=100:DIM A(N),B(N)
20 FOR I=1 TO N:B(I)=INT(RND(0)*1000):NEXT I
30 PRINT "SORTING ";N;" NUMBERS (JIFFIES)"
40 GOSUB 800:GOSUB 900:T0=T:GOSUB 1000:GOSUB 900:PRINT "BUBBLE:    ";T-T0:GOSUB 850
50 GOSUB 800:GOSUB 900:T0=T:GOSUB 2000:GOSUB 900:PRINT "INSERTION: ";T-T0:GOSUB 850
60 GOSUB 800:GOSUB 900:T0=T:GOSUB 3000:GOSUB 900:PRINT "SHELL:     ";T-T0:GOSUB 850
70 PRINT "ALREADY SORTED INPUT:"
80 GOSUB 900:T0=T:GOSUB 1000:GOSUB 900:PRINT "BUBBLE:    ";T-T0
90 GOSUB 900:T0=T:GOSUB 2000:GOSUB 900:PRINT "INSERTION: ";T-T0
100 GOSUB 900:T0=T:GOSUB 3000:GOSUB 900:PRINT "SHELL:     ";T-T0
110 END
800 FOR I=1 TO N:A(I)=B(I):NEXT I:RETURN
850 F=0:FOR I=2 TO N:IF A(I-1)>A(I) THEN F=1
860 NEXT I:IF F THEN PRINT "NOT SORTED!"
870 RETURN
900 T=PEEK(18)*65536+PEEK(19)*256+PEEK(20):RETURN

Line 850 checks every result, so a typing slip in a sort routine shows up at once as NOT SORTED!. Lines 70–100 sort the already sorted array again, which reveals how each method copes with data that is nearly in order.

2. Bubble sort

The bubble sort walks the list comparing neighbours and swaps any pair that is out of order. After one pass the largest value has "bubbled" to the end, so each pass can stop one place earlier. When a pass makes no swaps, the list is sorted.

1000 REM BUBBLE SORT
1010 M=N-1
1020 F=0:FOR I=1 TO M
1030 IF A(I)>A(I+1) THEN S=A(I):A(I)=A(I+1):A(I+1)=S:F=1
1040 NEXT I:M=M-1:IF F AND M THEN 1020
1050 RETURN

It is short and easy to get right, which is why it turns up in so many listings. Its weakness is that the work grows with the square of the list size: double the list and the sort takes about four times as long. Carl Evans timed a string-based bubble sort in Atari BASIC Faster and Better (1983). It took about 43 seconds for 50 items and almost three minutes for 100, and he estimated several hours for 1,000.

3. Insertion sort

Insertion sort works the way most people sort a hand of cards. It takes each item in turn, slides the larger items before it one place to the right, and drops it into the gap:

2000 REM INSERTION SORT
2010 FOR I=2 TO N:V=A(I):J=I-1
2020 IF A(J)<=V THEN 2040
2030 A(J+1)=A(J):J=J-1:IF J>0 THEN 2020
2040 A(J+1)=V:NEXT I:RETURN

It is still a "square law" sort, but it moves each item once instead of swapping it repeatedly, so it does roughly half the work of a bubble sort. On data that is already nearly sorted it is very fast. That makes it the right choice for adding a new score to a high-score table that is already in order.

Notice the two separate tests in lines 2020 and 2030. Atari BASIC evaluates every part of an AND, so IF J>0 AND A(J)>V would still look at A(J) when J is 0. That happens to be legal (arrays start at element 0), but in other cases the same pattern raises ERROR 9.

4. Shell sort

Donald Shell's 1959 idea was to run insertion sort on items far apart first, then closer, then adjacent. The early passes move badly misplaced items long distances in one jump, so the final ordinary insertion pass has almost nothing left to do. This version uses the gap sequence 1, 4, 13, 40, 121 … (each gap is three times the last plus one):

3000 REM SHELL SORT
3010 H=1
3020 H=3*H+1:IF H<=N THEN 3020
3030 H=INT(H/3):IF H<1 THEN RETURN
3040 FOR I=H+1 TO N:V=A(I):J=I-H
3050 IF A(J)<=V THEN 3070
3060 A(J+H)=A(J):J=J-H:IF J>0 THEN 3050
3070 A(J+H)=V:NEXT I:GOTO 3030

Only two lines differ from the insertion sort, and the gain is large. Evans's halving-gap Shell sort did 100 items in about 37 seconds, against three minutes for his bubble sort, and his 486-byte machine-language version did the same job in about four seconds.

5. The results

The screenshot above shows one run of the bench. It was made in an emulator running Altirra BASIC, which is compatible with Atari BASIC but generally faster, so expect bigger numbers on a real Atari BASIC cartridge. The comparison between the methods is the useful part:

100 numbers Random order Already sorted
Bubble 1666 jiffies (about 28 s) 19
Insertion 903 (about 15 s) 36
Shell 284 (under 5 s) 131

Shell sort is the best general-purpose choice: six times faster than bubble sort on random data, and the gap widens as the list grows. Bubble and insertion sorts win only when the data is already in order. The bubble sort's early exit after one swap-free pass makes it the fastest of all on a sorted list.

6. Sorting names: records in one string

Atari BASIC cannot DIM N$(10,8). The usual workaround is one long string divided into fixed-size fields, with record I at positions SZ*(I-1)+1 to SZ*I. You could sort by swapping substrings, but every swap copies the whole record three times through a temporary string. It is faster and simpler to leave the strings where they are and sort a numeric index array X(), which says which record comes first, second and so on:

10 SZ=8:N=10:DIM N$(SZ*N),T$(SZ),K$(SZ),B$(SZ),X(N)
20 N$(1)=" ":N$(SZ*N)=" ":N$(2)=N$:B$=N$(1,SZ)
30 FOR I=1 TO N:READ T$:N$(SZ*(I-1)+1,SZ*I)=T$:X(I)=I:NEXT I
40 DATA SMITH,JONES,ADAMS,MILLER,BAKER,YOUNG,CLARK,DAVIS,WILSON,TAYLOR
50 GOSUB 300
60 FOR I=1 TO N:P=SZ*(X(I)-1)+1:PRINT I;" ";N$(P,P+SZ-1):NEXT I
70 FOR R=1 TO 3:READ T$:K$=B$:K$(1,LEN(T$))=T$
80 GOSUB 500:PRINT T$;": ";
85 IF F THEN PRINT "FOUND AT ";F;" IN ";C;" PROBES"
90 IF F=0 THEN PRINT "NOT FOUND, ";C;" PROBES"
95 NEXT R:END
99 DATA MILLER,ADAMS,JACKSON
300 REM SHELL SORT OF INDEX X()
310 H=1
320 H=3*H+1:IF H<=N THEN 320
330 H=INT(H/3):IF H<1 THEN RETURN
340 FOR I=H+1 TO N:V=X(I):P=SZ*(V-1)+1:T$=N$(P,P+SZ-1):J=I-H
350 Q=SZ*(X(J)-1)+1:IF N$(Q,Q+SZ-1)<=T$ THEN 370
360 X(J+H)=X(J):J=J-H:IF J>0 THEN 350
370 X(J+H)=V:NEXT I:GOTO 330
500 REM BINARY SEARCH FOR K$
510 LO=1:HI=N:C=0:F=0
520 IF LO>HI THEN RETURN
530 M=INT((LO+HI)/2):P=SZ*(X(M)-1)+1:C=C+1
540 IF N$(P,P+SZ-1)=K$ THEN F=M:RETURN
550 IF N$(P,P+SZ-1)<K$ THEN LO=M+1:GOTO 520
560 HI=M-1:GOTO 520

Line 20 fills N$ with spaces using the self-copy trick and keeps an eight-space blank in B$. Line 30 stores each name in its field; shorter names keep the trailing spaces. The Shell sort at 300 is the same algorithm as before. It moves index numbers in X() and compares the records they point to. The program prints ADAMS to YOUNG in order.

The index approach has a bonus: you can keep several index arrays over the same data, one by surname and one by town, for example, without ever moving a record.

How strings compare

Atari BASIC compares two strings character by character, using ATASCII codes. At the first difference, the string with the lower code is "less". If one string runs out first and everything so far matched, the shorter string is less, so "SMITH"<"SMITHERS". Some consequences:

  • All capitals (65–90) sort before all lower-case letters (97–122), so "ZEBRA"<"apple". Store keys in one case.
  • A space (32) sorts before letters and digits, which is why space-padded fixed fields sort correctly.
  • Numbers stored as text sort by digit, not value: "9" comes after "27". Evans's fix is to pad numbers with leading zeros to a fixed width ("09", "27") and align decimal points, then use VAL to turn them back into numbers.

7. Binary search

Finding an item in an unsorted list means checking every entry: on average half of them. In a sorted list you can do far better. Look at the middle item. If it is too small, the target must be in the upper half, and if it is too large, the lower half. Each look halves the remaining range. Lines 500–560 above do exactly this through the index array. With 10 names, the program finds MILLER and ADAMS in 3 probes and decides JACKSON is missing after 4. A thousand sorted records need at most 10 probes, and a hundred thousand only 17.

When the search fails, LO is left pointing at the place where the item would go. This is the insertion point for adding a new record without re-sorting. The same routine works on a numeric array: replace the substring expressions with A(M) and compare against a number.

8. When BASIC is not enough

For a few hundred records, a Shell sort in BASIC is fine. Beyond that, call machine code with USR. Magazines published several ready-made routines: Adrian Dery's 182-byte machine-language bubble sort for multi-field records (Best of Antic, Volume 1), Evans's 486-byte Shell sort with key position, length and direction parameters, and Kevin Peck's Super Sorters in Antic (April and May 1988). The May part sorts numbers held as text correctly, including negatives and decimals. Dery also pointed out that turning off the screen with POKE 559,0 during a long sort gives the CPU about 30% more time. Restore the old value of 559 afterwards.

Troubleshooting

  • The bench prints NOT SORTED!. Compare your listing with the one above. A < typed for <=, or J+1 typed for J+H, is the usual cause.
  • ERROR 9 in a sort. An index ran past the array. Check the loop limits (N-1 in the bubble sort) and remember that Atari BASIC evaluates both sides of AND.
  • ERROR 5 when storing names. A name is longer than the field size SZ, or N$ was dimensioned too small. Use DIM N$(SZ*N).
  • Names come out in a strange order. Mixed case, or leading spaces in the DATA. Print each field between quotes to see what is actually stored.
  • A binary search misses items that are there. The list is not sorted by the same key and the same comparison, or the search key was not padded to the field width the way the records were. Line 70 shows the padding.

Further reading

  • Atari BASIC Faster and Better by Carl M. Evans (IJG, 1983), Chapter 10, "Sorting Things Out": BASIC bubble and Shell sorts, a relocatable machine-language Shell sort and multi-key sorting.
  • Antic, April and May 1988: Kevin Peck's two-part Super Sorters (Multikey Sort, then Mixed Numbers sorting and a string-find routine).
  • Best of Antic, Volume 1: Adrian Dery's Bubble Sort machine-language utility.
  • The Art of Computer Programming, Volume 3: Sorting and Searching by Donald E. Knuth: the standard reference.
  • On this site: Atari BASIC String Handling and Tricks, Making Atari BASIC Faster, Calling Machine Language from Atari BASIC with USR and Working with Disk Files in Atari BASIC.

Credits