Sorting Through The TS2068 Sorts

This article compares the sorting speed of three routines on randomized, inverted and ordered data. The listing uses REM statements so that you can tell where each of the sorting routines begins. During the testing, only one routine was programmed at a time so that routines near the end of the program would not be slowed by GO TO instructions stepping over unnecessary lines at the beginning (a Sinclair Basic quirk).

Quicksort #1 is from an article in Sync Magazine (March 84), and is included simply because it represents the only article I have seen on advanced sorting routines for the Timex. Its extensive memory requirements (413 bytes + 10 for each item to be sorted) makes it impractical for most uses. As seen on the chart, there are better solutions, so I didn’t include this one in the program listing.

Quicksort #2 comes from an article in Creative Computing (May 83), which I have adjusted to work on the 2068. It is almost identical in speed to Quicksort #1, and although it requires 1084 bytes, it does not require more for each item to be sorted and will use less memory in most situations.

The Shell-Faulk routine is actually an improvement over the Shell-Metzner sort and is not only faster, but it also uses less memory (227 bytes). It is the one I use on my T/S Grader for the 2068 because of its overall versatility. Besides being easy on your computer’s memory, it is the fastest at sorting random strings until you have 800 or more (even then the difference is small), and it will go through already sorted material or invert that material even faster.

Note on the chart how slow the Quicksorts are on anything besides random data! The Shell-Faulk is found twice in the listing, once using multi-statement lines and the other using single statement lines for the 1000.

Some categories on the chart have not been filled in because the trends became obvious, and I saw no reason to wait hours for the quicksorts to go through the data. Quicksort #1 uses too much memory to allow 3200 strings to be sorted.

The reason for sorting material that is already in order is two-fold. First, you may not remember if it was previously sorted and so sort again to be sure. Secondly, many routines slow down on “almost sorted” data, such as, when adding a file to a previously sorted list. Since there is no precise definition of “almost sorted,” I just left the data ordered to be consistent.

Since the Table 1. results are somewhat misleading, I ran a special test with the Shell-Faulk and Quicksort #2 on an ordered list of 400 items. I changed the last item to be the first and timed how long it took each to reorder the data. The Shell Faulk took 82 seconds while the Quicksort took 1164 seconds. Although the gap narrowed considerably, the Shell-Faulk was still far superior.

   1 REM X=NUMBER OF FILES              L=LENGTH OF EACH FILE          N$(X,L) HOLDS ALL FILES
 100 REM = SET UP RANDOM FILES
 110 LET X=100: LET L=10: DIM N$(X,L): FOR Z=1 TO X: FOR N=1 TO L: LET N$(Z,N)=CHR$ INT (65+RND*26): NEXT N: NEXT Z: PRINT "READY": BEEP .5,40: PAUSE 0
1000 REM = SHELL-FAULK SORT FOR                 THE 2068
1050 LET M=X: LET S=M
1100 LET S=INT (S/2): IF S<1 THEN GO TO 9900
1115 IF S/2=INT (S/2) THEN LET S=S+1
1120 FOR N=1 TO M-S: LET J=N
1150 IF N$(J)>N$(J+S) THEN LET D$=N$(J): LET N$(J)=N$(J+S): LET N$(J+S)=D$: LET J=J-S: IF J>0 THEN GO TO 1150
1160 NEXT N: GO TO 1100
2000 REM = SHELL-FAULK SORT FOR                 THE 1000
2050 LET M=X
2055 LET S=M
2100 LET S=INT (S/2)
2105 IF S<1 THEN GO TO 9900
2115 IF S/2=INT (S/2) THEN LET S=S+1
2120 FOR N=1 TO M-S
2130 LET J=N
2140 IF N$(J)<=N$(J+S) THEN GO TO 2160
2143 LET D$=N$(J)
2145 LET N$(J)=N$(J+S)
2150 LET N$(J+S)=D$
2155 LET J=J-S
2157 IF J>0 THEN GO TO 2140
2160 NEXT N
2165 GO TO 2100
4000 REM = QUICKSORT #2 FOR 2068
4100 DIM P(20): DIM W(20): LET N=0: LET C=0: LET K=1: LET P(K)=1: LET W(K)=X: LET L=1: LET R=X
4110 IF (R-L)<9 THEN GO TO 4240
4120 LET I=L: LET J=R
4130 LET C=C+1: IF N$(I)>N$(J) THEN GO TO 4180
4140 LET J=J-1: IF J>I THEN GO TO 4130
4150 LET J=J+1
4160 LET K=K+1: IF (I-L)<(R-J) THEN GO TO 4230
4170 LET P(K)=L: LET W(K)=I: LET L=J: GO TO 4110
4180 LET N=N+1: LET D$=N$(J): LET N$(J)=N$(I): LET N$(I)=D$: GO TO 4200
4190 LET C=C+1: IF N$(J)<N$(I) THEN GO TO 4220
4200 LET I=I+1: IF J>I THEN GO TO 4190
4210 LET J=J+1: GO TO 4160
4220 LET N=N+1: LET D$=N$(J): LET N$(J)=N$(I): LET N$(I)=D$: GO TO 4140
4230 LET P(K)=J: LET W(K)=R: LET R=I: GO TO 4110
4240 IF (R-L+1)=1 THEN GO TO 4280
4250 FOR I=(L+1) TO R: FOR J=L TO (I-1): LET Y=I-J+L-1: LET C=C+1: IF N$(Y)<=N$(Y+1) THEN GO TO 4270
4260 LET N=N+1: LET D$=N$(Y): LET N$(Y)=N$(Y+1): LET N$(Y+1)=D$: NEXT J
4270 NEXT I
4280 LET L=P(K): LET R=W(K): LET K=K-1: IF K=0 THEN GO TO 9900
4290 GO TO 4110
9900 REM = PRINT ORDERED FILES
9910 BEEP .5,30: FOR N=1 TO X: PRINT N$(N): NEXT N

When you type in the listing, you should only enter the lines for the routine that you want since only the first listing will sort anyway.

The 1000 can only use one of the routines as written, but you will have to change the PAUSE 0 to PAUSE 4E4, and forget the BEEP statement.

When the program prints “READY,” just press a key to start sorting.

There are two changes that you may wish to make in the listing. As shown, the routines only alphabetize strings, but you may want to invert the order or sort numbers instead.

To invert the order, make the following changes:

1. Line 1150 – change the > in the first statement to a <.

2. Line 2140 – change the <= to >=.

3. Line 4130 – change the < to >.

4. Line 4190 – change the < to >.

5. Line 4250 – change the <= to >=.

To sort numeric arrays change all references to N$() to just N() and D$ to just D. Also, when setting up the numeric array, it should have just one dimension instead of the two used for strings.

If you have a better routine or can improve on these, drop me a line and I’ll do a follow up if necessary. I would also be interested in machine code sorting routines for string and numeric arrays.

Table 1.
Comparison of Sorting Times
for three different sort routines

SORT                  Number of strings to sort
Routine Type    50     100    200    400    800    1600   3200

Quick   R       14.4   34.1   80.2   177    421    887    Beyond
Sort    I       42.5   168                                Capacity
#1      S       43.2   169

Quick   R       14.3   33.8   77.6   184    403    884    1977
Sort    I       41.4   152    564    2286
#2      S       37.4   145    551    2190

Shell   R       11.8   29.9   74.8   184    430    1049   2402
Faulk   I       10.1   23.2   56.6   126    278    629    1427
Sort    S       4.7    11.2   26.4   61     131    293    685

Key:
R-Random
I-Inverted
S-Sorted

Times in seconds on 2068
Averages of 8 test runs each
Files of 10 strings each