Instant Sorting

In the May-June ’86 issue of SyncWare News, I went through several sort routines for the 2068 and 1000 computers. For general use, I decided that the Shell-Faulk was the best all-round choice, but I also asked readers to send in any better ideas. One reader did, Larry Crawford of London Ontario, Canada. He took the Shell-Faulk and converted it to machine code. Between the two of us, we have worked out bugs, shortened it, and made it more flexible. This routine will work on either the 2068 or Spectrum, but it should only take a little hacking to convert to a 1000.

conSORTING with Speed

Let’s get right to the issue of speed. Below is a comparison of the Shell-Faulk in BASIC and machine code at sorting files which are each 10 characters long.

                  BASIC           MACHINE CODE

  50 files =     11.8 sec             .2 sec
 100       =     29.9                 .3
 200       =     74.8                 .7
 400       =    184.0                1.8
 800       =    430.0                4.9
1600       =   1049.0               15.0
3200       =   2402.0               47.0

Maybe instant isn’t the best word for it, but I think most people would be happy with this much speed. It works with any two dimensional string array (this is not for numbers – sorry) with any name and you can change the dimensions at will. A few BASIC statements relay certain key bits of information to the machine code before it is called.

Sorting out the Code

First type in the following lines of BASIC:

  10 LET X=100: LET L=10: DIM N$(X+1,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
  20 POKE 23296,X-256*INT (X/256): POKE 23297,INT (X/256): POKE 23298,L-256*INT (L/256): POKE 23299,INT (L/256): LET N$(X+1)=N$(X+1): POKE 23300,PEEK 23629: POKE 23301,PEEK 23630
  30 LET N$(1)=N$(1): RANDOMIZE USR 61402
 100 BEEP .5,30: FOR Z=1 TO X: PRINT N$(Z): NEXT Z: STOP
9990 CLEAR 61389: LOAD "sort"CODE 61390: GO TO 1
9999 SAVE "SORT" LINE 9990: BEEP .5,40: SAVE "sort"CODE 61390,249: BEEP .5,40: CLS: PRINT "REWIND TO VERIFY": VERIFY "SORT": VERIFY "sort"CODE 61390,249

Line 10 just sets up some random files for testing purposes as was done in the BASIC version of the sort. One change is that we dimension N$ for one extra file space. Thus, if X=100 we actually dimension N$(101,L). This extra space is only used as a temporary storage area as files are moved. Never use it to store data. Be sure to set up this extra file space in your own programs too. As you test this program, feel free to set X (the number of files) and L (the length of files) to any values the computer has room for. If your own programs do not use N$ for storage, just change all references to N$ to be the name you want. The same applies to the use of X and L.

Line 20 begins the part of the routine you use in your own programs. It sets up the machine code pointers beginning with POKE 23296 and 23297 with the number of files to sort (X) not including the extra file. You could POKE a lower value than X if you only wanted to sort some of the files such as the first 50. Next we POKE the length of each file into 23298 and 23299. The two storage areas for size and length are to allow values larger than 255. This way you can have thousands of values of considerable length.

The statement LET N$(X+1)=N$(X+1) is used to make the computer store the address of the extra file in a special place called “dest”. This is found at 23629 and 23630. Therefore we take the contents of those addresses and put them in 23300 and 23301 so the machine code can access it later.

All these POKES are made into the printer buffer as are all variables created by the machine code itself. This is one reason the program is completely relocatable. If you do relocate the machine code, do not change the location of any POKES!

file to sort, but instead of poking the location as before, we let the machine code access “dest” directly. You can make the routine start sorting after the first file if you wish. To start with the 11th file, just make the statement read: LET N$(11)=N$(11). Also be sure you have adjusted the total number of files to sort as well. If X=100, then by starting at file number 11, we would only sort 90 files. Without this correction, the routine would overwrite other variables. The machine code is then called and the sorting is done.

Lines 20 and 30 are the only BASIC lines you need to use this in your own programs. The actual line numbers are not important and the two lines can be combined if you wish. The remaining lines are only used to allow you to practice on this example, but are not needed in your programs. Line 100 prints out the sorted files. Line 9999 is for making a copy of the program (enter RUN 9999) and verifying it after the machine code is in place. When reloaded, line 9990 sets RAMTOP and loads the machine code. The test procedure then begins. Depending on the values you set for X and L, the setup can take quite some time – certainly longer than the sorting process. After you have saved a copy, you can test without reloading by entering RUN.

The machine code can be moved to any position you prefer as long as you have room for 249 bytes. Remember that the RANDOMIZE USR address must be 12 bytes past the start of the machine code. If you load it in at 65000, then RANDOMIZE USR 65012. Also adjust the save and load commands to reflect the change.

To enter the machine code, first enter CLEAR 61389. Now enter the following lines which will load the machine code beginning at 61390:

1000 FOR N=61390 TO 61638
1010 INPUT "ENTER NUMBER ";P
1015 POKE N,P
1020 PRINT N;" ";P
1030 NEXT N
1040 STOP

Now enter RUN 1000 and then enter one number at a time as listed below. The numbers are listed in order horizontally so finish the first row ACROSS before going to the second line.

 17   0  91  33  22  91   1  21   0 237
176 201  42   0  91  34  10  91  34  12
 91  42  12  91 175 203  28 203  29 124
181  40 223 203 197  34  12  91 229 235
 42  10  91 175 237  82  34  14  91  33
  1   0  34  16  91  34  18  91  42  77
 92  34   6  91 237  91   2  91 193  25
 11 120 177  32 250  34   8  91 237  91
  6  91 237  75   2  91  26 190  56  11
 32  62  11 120 177  40   4  19  35  24
241  58  20  91  61  32  11 225  34   8
 91 225  34   6  91  50  20  91  42  16
 91  35  34  16  91  34  18  91 235  42
 14  91 175 237  82  56 140  42   6  91
237  91   2  91  25  34   6  91  42   8
 91  25  24 177  42   6  91 237  91   4
 91 237  75   2  91 213 197 229 237 176
 42   8  91 209 193 229 197 237 176 193
209 225 237 176  42  18  91 237  91  12
 91 175 237  82  34  18  91  56 158  40
156  58  20  91 254   0  32  12  42   6
 91 229  42   8  91 229  60  50  20  91
 42   6  91  34   8  91 229 237  75   2
 91 237  91  12  91 175 237  66  27 122
179  32 248  34   6  91 225  24 159

When all the numbers have been entered, delete all lines from 1000 to 1040 and make your backup copy before testing the program.

MC Explained

The logic of the machine code closely follows that of the BASIC version. As I explain the machine code, I will refer to the original BASIC version often so here is a listing of the sort portion of that routine so you can better follow along:

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

Here is a description of the machine code:

EFCE LD DE,5B00      The start of the machine code is at 61390. This is actually the end of the sort where the printer buffer is cleared of data. DE is set to the start of the buffer which is also the start of the machine code variables.
EFD1 LD HL,5B16      HL is set to a point in the buffer that is not affected by the mc and still contains zeros.
EFD4 LD BC,0015      BC holds the number of bytes affected by the machine code routine.
EFD7 LDIR            This command moves whatever is in the address represented by HL into the DE address. HL and DE are each incremented to the next address while BC is reduced by 1. This repeats until BC=0 which also means the buffer is clear so your next LPRINT won't print any garbage.
EFD9 RET             Return to BASIC (sort done)
EFDA LD HL,(5B00)    The actual sort starts here from BASIC (address 61402). HL is loaded with the value of X which was poked into 5B00 from BASIC.
EFDD LD,(5B0A),HL    Put X in storage for M. Same as M=X in line 1050.
EFE0 LD (5B0C),HL    Also put in storage for S. Same as S=M in line 1050.
EFE3 LD HL,(5B0C)    This starts line 1100. Get value of S
EFE6 XOR A           Clears carry flag before RR instruction and zero the A register
EFE7 RR H
EFE9 RR L            These 2 instructions get the integer value of HL/2. Thus it is the same as INT (S/2) in 1100.
EFEB LD A,H
EFEC OR L
EFED JR Z,EFCE       If HL=0 (S=0) then sort is done so jump to clear printer buffer before going to BASIC
EFEF SET 0,L         Set bit zero of L to make sure it is an odd value (line 1115).
EFF1 LD (5B0C),HL    Store new value of S.
EFF4 PUSH HL         Push S on stack.
EFF5 EX DE,HL        Put S value in DE
EFF6 LD HL,(5B0A)    Get M value
EFF9 XOR A           Clear carry flag before subtraction
EFFA SBC HL,DE       Calculate M-S
EFFC LD (5B0E),HL    Store M-S
EFFF LD HL,0001      Prepare for FOR-NEXT loop
F002 LD (5B10),HL    Store in N. Thus loop starts as N=1
F005 LD (5B12),HL    Put in J (J=N). See line 1120
F008 LD HL,(5C4D)    5C4D is the address of "dest", so this shows where the first file is.
F00B LD (5B06),HL    Store address of first file in N$(J)
F00E LD DE,(5B02)    Get the length of each file
F012 POP BC          Get S value
F013 ADD HL,DE
F014 DEC BC
F015 LD A,B
F016 OR C
F017 JR NZ,F013      These lines find the address of file N$(J+S)
F019 LD (5B08),HL    Store N$(J+S) address. See 1150
F01C LD DE,(5B06)    Get N$(J) address
F020 LD BC,(5B02)    Get file length
F024 LD A,(DE)       Get a character from N$(J) file
F025 CP (HL)         Compare to character in N$(J+S) file
F026 JR C,F033       Jump if the order is okay to the preparation for NEXT N
F028 JR NZ,F068      Jump to swap routine if order is wrong
F02A DEC BC          If the characters are the same then we continue to compare the two files by first decrementing the number of file characters to check.
F02B LD A,B
F02C OR C
F02D JR Z,F033       These lines check to see if BC=0, thus all characters are checked. If so then jump to NEXT N.
F02F INC DE
F030 INC HL
F031 JR F024         To continue comparing the two files, we move HL and DE to the next characters and jump back to compare again.
F033 LD A,(5B14)     This starts the preparation for NEXT N.
F036 DEC A           Since the FLAG was either zero or one, this will make it zero or 255.
F037 JR NZ,F044      If it is 255, the flag was not set so jump to NEXT N.
F039 POP HL          If the flag was set, get old N$(J+S) address. This is the address before we did LET J=J+S in line 1150.
F03A LD (5B08),HL    Store LET J=J+S in line 1150.
F03A LD (5B08),HL    Store in N$(J+S)
F03D POP HL          Get old N$(J) - what it was before LET J=J-S.
F03E LD (5B06),HL    Store in N$(J)
F041 LD (5B14),A     The A register is zero so this clears the FLAG.
F044 LD HL,(5B10)    NEXT N begins here. First get old N value.
F047 INC HL          To next value of FOR-NEXT loop
F048 LD (5B10),HL    Store new N value
F04B LD (5B12),HL    Store in J too (J=N)
F04E EX DE,HL        Put J value in DE
F04F LD HL,(5B0E)    Get M-S value
F052 XOR A           Clear carry flag
F053 SBC HL,DE       Subtract (M-S)-J to see if FOR-NEXT is done.
F055 JR C,EFE3       If J is more than M-S, then the loop is done so jump back to mc version of line 1100.
F057 LD HL,(5B06)    If loop is not done, get N$(J) address.
F05A LD DE,(5B02)    Get length of file
F05E ADD HL,DE       Puts HL at next file
F05F LD (5B06),HL    Store new N$(J) address
F062 LD HL,(5B08)    Get N$(J+S) address
F065 ADD HL,DE       HL at next file (new N$(J+S) address).
F066 JR F019         Go back and sort again
F068 LD HL,(5B06)    Start the file swap here. Get N$(J) address.
F06B LD DE,(5B04)    Load DE with the extra N$ file address which is used as D$ in the BASIC version.
F06F LD BC,(5B02)    Get file length so we know how many bytes to move.
F073 PUSH DE         Save D$ address
F074 PUSH BC         Save file length
F075 PUSH HL         Save N$(J) address
F076 LDIR            Put file N$(J) in D$
F078 LD HL,(5B08)    Get N$(J+S) address
F07B POP DE          Get N$(J) address
F07C POP BC          Get length of file
F07D PUSH HL         Save N$(J+S)
F07E PUSH BC         Save length
F07F LDIR            Put N$(J+S) in N$(J)
F081 POP BC          Get length
F082 POP DE          Get N$(J+S) address
F083 POP HL          Get D$ address
F084 LDIR            Put D$ in N$(J+S)
F086 LD HL,(5B12)    Get J value
F089 LD DE,(5B0C)    Get S value
F08D XOR A           Clear carry flag
F08E SBC HL,DE       Calculate J-S
F090 LD (5B12),HL    Store new J value
F093 JR C,F033
F095 JR Z,F033       If J is less or equal to zero, then go to prep fN.
F097 LD A,(5B14)     This starts our preparation to go line 1150. First get FLAG.
F09A CP 00           Compare FLAG to zero
F09C JR NZ,F0AA      Jump if FLAG already set
F09E LD HL,(5B06)    If FLAG is not set, we must save the present address of N$(J), so first get N$(J) address.
F0A1 PUSH HL         Save N$(J) address
F0A2 LD HL,(5B08)    Get N$(J+S) address to save too
F0A5 PUSH HL         Save it
F0A6 INC A           Make A register hold 1
F0A7 LD (5B14),A     Use it to set FLAG
F0AA LD HL,(5B06)    Get N$(J) address
F0AD LD (5B08),HL    Put it in N$(J+S). This allows for LET J=J-S.
F0B0 PUSH HL         Save address of N$(J+S)
F0B1 LD BC,(5B02)    Get file length
F0B5 LD DE,(5B0C)    Get S value
F0B9 XOR A           Clear carry flag
F0BA SBC HL,BC
F0BC DEC DE
F0BD LD A,D
F0BE OR E
F0BF JR NZ,F0B9      These adjust the address of N$(J) because of the LET J=J-S command.
F0C1 LD (5B06),HL    Store new N$(J) address
F0C4 POP HL          Get N$(J+S) address
F0C5 JR F066         Now go back to sort again. The jump is too far for a relative jump so it is done in two steps. First to F066 which then goes to F019.

The variables are all found in the printer buffer as follows:

5B00-5B01 (23296-7)  X value from BASIC
5B02-5B03 (23298-9)  Length of file from BASIC
5B04-5B05 (23300-1)  Extra file address from BASIC
5B06-5B07 (23302-3)  N$(J) address
5B08-5B09 (23304-5)  N$(J+S) address
5B0A-5B0B (23306-7)  M value
5B0C-5B0D (23308-9)  S value
5B0E-5B0F (23310-1)  M-S value
5B10-5B11 (23312-3)  N value
5B12-5B13 (23314-5)  J value
5B14      (23316)    FLAG

As always, let me know if you have any better ideas (BASIC or machine code). The address is: Robert C. Fischer; [address omitted]