Apart from personal interest and/or intellectual stimulation, there is little point in adopting a partisan approach to machine code. It is pointless to view BASIC, particularly BBC BASIC, as a language inferior to machine code. The two should complement, rather than rival, each other. Once familiarity and confidence is gained in handling machine code, it will gradually become clear which parts of a BASIC program should be relegated to machine code and which parts can be handled quite adequately in BASIC.
There can be no doubt, however, that one area in data processing which calls out for machine code solutions is sorting data into numerical or alphabetical order. It has been stated that approximately 30% of all commercial computing time is spent on some kind of sorting activity. An ordered system of any kind represents a 'high energy' system. Since the equation for energy in physics is power multiplied by time, we would therefore expect that programs which sort data will make heavy demands on computing time.
The physical power of a given computer is fixed by the hardware, which in turn depends on such things as the clock frequency, word length and the sophistication built into the central processor (in the BBC, the central processor is the 6502). Although in no way meant as criticism, the machine, and indeed most other microcomputers likely to be found in the average borne, arc slow in terms of 'mips' (million instructions per second). The BBC machine is rated at about 0-5 mips. In contrast, some of the modern mainframe giants have reached a speed approaching 100 mips with a word length of 64 bits and it is confidently expected that this figure will be substantially beaten by the forthcoming breed of fifth generation machines. Returning to present day reality, there is nothing we can do about the limitations imposed by the hardware of our machine. The only method of attack is to use software which takes the fullest advantage of the machine.
This chapter is devoted entirely to the problem of machine code sorting routines. A simple bubble sort, limited to single byte data, was introduced in the previous book, Discovering BBC Micro Machine Code. The following programs treat the sorting problem in more detail and will include the sorting of arrays of four-byte BASIC integers, strings, floating point numbers and two-dimensional string arrays. It will also include routines which sort fixed length multi-field records. They are given complete with BASIC parameter passing lines so they can be entered and exhaustively tested. It should be pointed out that the machine code portion of the listings will stand alone as subroutines, providing that:
All the programs in this chapter are concerned with sorting data into either numerical or alphabetical order and will be useful in compiling indexes, customer lists, domestic accounts, hobby collections (butterflies, stamps, beetles) etc. They could also be employed as routines within general purpose filing systems to store or retrieve information according to some predetermined order.
The bubble sort is well-known but often despised because it is slow. It is one of the simplest sort routines to understand and, providing there are not too many elements in the array, can be acceptable if written in machine code. It provides a good starting point for handling multibyte integers.
Because the programs which follow are intended to be used in conjunction with BASIC, via CALL parameters, it is important to understand how the interpreter allocates variable space.
The four bytes, allocated to each integer array variable, are arranged as follows:
Fig. 6.1. Flowchart for integer array bubble sort.
Each integer of the array is then stored sequentially, so in effect, each element has an address 4 bytes in advance of the previous integer.
The machine code routine is executed from BASIC via the CALL statement:
CALL SORT, NUMBER%, ARRAY%(1)
Of course, the above variable names are arbitrarily chosen but they must be in the above order where:
Fig. 6.2. Expansion of block 7 in Fig. 6.1.
SORT=the start address of the routine
NUMBER%=the number of elements in the array
ARRAY%(1) the first usable element in the array
The zero element is best left vacant for headings, etc.
The flowchart for the routine is given in Fig. 6.1. As can be seen, the algorithm consists basically of an inner control loop and an outer control loop. The pairs of integers are repeatedly incremented, compared (and if necessary swopped) in the inner loop. The largest integer in the list always 'bubbles' through to the last position. It will no longer be necessary to involve this integer again, so the outer loop count may be reduced by one. On the next inner loop series of cycles, the next largest integer 'bubbles' through to the last but one position in the list and so on, until the list is fully sorted. The maximum number of comparisons is approximately equal to half the square of the array size. The execution time can be reduced if the list is not too disordered by the use of a swop flag technique as shown in the flowchart. Note from the flowchart that the blocks have been numbered for reference purposes. Block 7 is shown expanded in Fig. 6.2. The listing corresponding to the flowchart is given in Program 6.1
Program 6.1. Bubble sort of an unsigned 32-bit integer array
10 REM BUBBLE SORT OF ARRAY OF
20 REM 32bit UNSIGNED INTEGERS
30 NUMBER=&70:CYCLE=&72:POINTER1=&74
40 POINTER2=&76:FLAG=&78
50 DIM SORT 500
60 FOR PASS=0 TO 2 STEP 2
70 P%=SORT
80 [OPT PASS \***************
90 LDA &0601 \SET NUMBER OF
100 STA CYCLE \BASIC INTEGERS
110 LDA &0602 \IN ARRAY AND
120 STA CYCLE+1 \STORE IN NUMBER
130 LDY #1
140 LDA (CYCLE),Y
150 STA NUMBER+1
160 DEY
170 SEC
180 LDA (CYCLE),Y \***************
190 SBC #1 \DECREMENT
200 STA NUMBER \NUMBER
210 BCS OUTERLOOP \***************
220 DEC NUMBER+1
230 .OUTERLOOP \***************
240 LDA #0 \INITIALISE
250 STA FLAG \SWOP FLAG AND
260 STA CYCLE \CYCLE TO ZERO
270 STA CYCLE+1
280 LDA &0604 \***************
290 STA POINTER2 \STORE FIRST INT
300 LDA &0605 \ADDRESS TEMP IN
310 STA POINTER2+1 \POINTER2
320 .INNERLOOP \***************
330 LDA POINTER2+1 \TRANSFER
340 STA POINTER1+1 \POINTERS
350 LDA POINTER2 \POINTER1 =
360 STA POINTER1 \POINTER2
370 CLC \
380 ADC #4 \ADD 4 TO
390 STA POINTER2 \POINTER 1 AND
400 BCC SKIP \STORE IN
410 INC POINTER2+1 \POINTER2
420 .SKIP \***************
430 LDX #4 \SUBTRACT INT'S
440 LDY #0 \A BYTE AT A
450 SEC \TIME (4 BYTES)
460 .COMPLOOP \KEEPING TRACK
470 LDA (POINTER2),Y \OF CARRY FLAG
480 SBC (POINTER1),Y \AT COMPLETION
490 INY
500 DEX
510 BNE COMPLOOP \BRANCH NOSWOP
520 BCS NOSWOP \IF CARRY SET
530 DEY
540 STY FLAG \SET SWOP FLAG
550 .SWOPLOOP \***************
560 LDA(POINTER1),Y \SWOP INTEGERS
570 TAX \A BYTE AT A
580 LDA(POINTER2),Y \TIME
590 STA(POINTER1),Y
600 TXA
610 STA(POINTER2),Y
620 DEY
630 BPL SWOPLOOP
640 .NOSWOP
650 INC CYCLE \***************
660 BNE SKIP2 \INCREMENT
670 INC CYCLE+1 \CYCLE
680 .SKIP2 \***************
690 LDA CYCLE \COMPARE CYCLE
700 CMP NUMBER \TO NUMBER. IF
710 BNE INNERLOOP \<> BRANCH TO
720 LDA CYCLE+1 \INNERLOOP
730 CMP NUMBER+1
740 BNE INNERLOOP
750 LDA FLAG \IF SW.FLG CLEAR
760 BEQ FLAGCLEAR \BR. FLAGCLEAR
770 LDA NUMBER \***************
780 SEC \DECREMENT
790 SBC #1 \NUMBER
800 STA NUMBER
810 BCS SKIP3
820 DEC NUMBER+1
830 .SKIP3 \***************
840 LDA NUMBER \COMPARE NUMBER
850 BNE OUTERLOOP \TO ZERO
860 LDA NUMBER+1 \BRANCH IF <> TO
870 BNE OUTERLOOP \OUTERLOOP
880 .FLAGCLEAR
890 RTS:]
900 NEXT PASS
910
920 REM BASIC IS FOR TESTING ONLY
930 MODE4
940 CLS
950 INPUT"NUMBER OF INTEGERS ",NUMBER%
960 PRINT
970 DIM ARRAY%(NUMBER%)
980 FOR N%=1 TO NUMBER%
990 ARRAY%(N%)=RND(10000)
1000 PRINT ARRAY%(N%)
1010 NEXT
1020 PRINT
1030 PRINT "SORTING"
1040 PRINT
1050 START%=TIME
1060 CALL SORT,NUMBER%,ARRAY%(1)
1070 time%=TIME-START%
1080 FOR N%=1 TO NUMBER%
1090 PRINT ARRAY%(N%)
1100 NEXT
1110 PRINT
1120 PRINT"SORTING TIME= ";time%/100;"
SECONDS"
Although the listing is supplied with outline remarks, here is a more detailed breakdown:
Lines 30-40 set up the zero-page labelled locations referred to in assembly code.
Lines 90-220 obtain the address of the BASIC variable NUMBER£% from the CALL parameter block and temporarily store it in CYCLE. Using indirect indexed addressing, the data is picked up, decremented by 1 and stored in NUMBER and NUMBER+1 (low-byte and high-byte respectively). Note, that zero-page locations must be used for indirect indexed addressing.
Lines 240-270 initialise the swop FLAG and CYCLE counter to zero.
Lines 280-310 store the address of the first integer in the array temporarily in POINTER2. This is picked up from the CALL parameter block.
Lines 320-360 copy POINTER2 contents into POINTER1.
Lines 370-410 add 4 to POINTER1 and store the result in POINTER2.The reason why 4 is added is so that POINTER2 is the address of the next integer in the array: that is to say, 4 bytes onwards.
Line 430 initialises the byte counter to 4. The X register is used for this (see below).
Lines 450-520 subtract the integers with carry, a byte at a time, keeping the result of the fourth bytes in the accumulator. Notice that the X register and DEX is used for byte counting. This is because a CPY instruction would corrupt the carry flag during the subtraction processes. If the carry flag is set at the end of the subtraction, no swop is required. This method only works for unsigned integers.
Line 530 sets the byte counter for the swop process. DEY is used to set this to 3 since the current value of Y is 4.
Line 540 stores the Y register contents as a swop flag in FLAG (any nonzero quantity would do here).
Lines 560 to 630 swop the integers, a byte at a time, starting with the high-byte. Notice that the X register is used as a temporary storage location as this is the most economical in execution time since TAX uses only two machine cycles, whereas the alternatives PHA or STA require 3 cycles.
Lines 650-680 increment the CYCLE counter by 1. The coding given is an economical way to do this in terms of execution time.
Lines 690-740 compare the low-byte of CYCLE and NUMBER. If the resuit is non-zero, a branch is made to the label INNERLOOP. If the result is zero, the program 'falls through' to compare the high-byte in the same manner.
Lines 750-760 check if the swop FLAG is clear. If so, a branch to FLAGGLEAR is made.
Lines 770-820 decrement NUMBER by 1 (2 bytes, of course).
Lines 840 to 870 check if NUMBER has reached zero, first checking the low-byte with branching to OUTERLOOP if not true- otherwise 'falling through' to compare the high-byte.
Lines 920-1120 are pure BASIC just for test and familiarisation purposes. They first print out a random integer array, call the machine code routine and then print out the sorted result together with the time taken. See Table 6.1 at the end of this chapter for a compendium of timing data.
Fig. 6.3. Block 7 expansion for string array sort
This routine is capable of sorting a BASIC string array, where the string elements can vary in length up to the legal maximum of 255.
When a string array is set up by the interpreter, four bytes are used in a similar manner to integers. These bytes are not the strings themselves but length details and the address of where the string is actually stored. These four bytes are referred to as a String Information Block, the details of which follow:
The actual string, consisting of the ASCII codes in sequential memory locations, is stored from the starting address given in bytes I and 2 above. A string array is formed by a series of such string information blocks, stored sequentially in memory. Therefore, if we want to swop strings (such as during a string sort) it is necessary only to swop the string information blocks since these tell the system where the strings are stored. This makes programs involving machine code sorting much easier to program since most of the work has already been done by the interpreter. Byte 3 of the String Information Block gives the maximum number of characters allowed before discarding original reserved space. [his data is rarely used in practice, except in 'housekeeping' or garbage disposal programs and consequently is of no present interest to us. Byte 4 of the String Information Block gives the actual length of the string in bytes (characters).
The CALL parameter block is first set up in BASIC and requires the following variables in the CALL statement:
CALL SORT, NUMBER%, ARRAY$(1)
The above call is in the same form as that of the previous call, except that ARRAY$(1) is used.
The flowchart is essentially the same as Fig. 6.1 with one proviso, the details of block 7. The flowchart, showing the amendment is given in Fig. 6.3. The listing is given in Program 6.2.
Program 6.2. String array bubble sort.
10 REM STRING ARRAY BUBBLE SORT
20 REM WITH VARIOUS LENGTH STRINGS
30 NUMBER=&70:CYCLE=&72:POINTER1=&74
40 POINTER2=&76:FLAG=&78:string1=&79
50 string2=&7B:length1=&7D
60 length2=&7E
70 DIM SORT 500
80 FOR PASS=0 TO 2 STEP 2
90 P%=SORT
100 [OPT PASS \***************
110 LDA &0601 \GET NUMBER OF
120 STA CYCLE \BASIC STRINGS
130 LDA &0602 \IN ARRAY AND
140 STA CYCLE+1 \STORE IN NUMBER
150 LDY #1
160 LDA (CYCLE),Y
170 STA NUMBER+1
180 DEY
190 SEC
200 LDA (CYCLE),Y \***************
210 SBC #1 \DECREMENT
220 STA NUMBER \NUMBER
230 BCS OUTERLOOP
240 DEC NUMBER+1
250 .OUTERLOOP \***************
260 LDA #0 \INITIALISE
270 STA FLAG \SWOP FLAG AND
280 STA CYCLE \CYCLE TO ZERO
290 STA CYCLE+1 \***************
300 LDA &0604 \STORE START
310 STA POINTER2 \ADDRESS OF
320 LDA &0605 \$ INF BLOCK IN
330 STA POINTER2+1 \POINTER2 TEMP.
340 .INNERLOOP \***************
350 LDA POINTER2+1 \TRANSFER
360 STA POINTER1+1 \POINTERS
370 LDA POINTER2 \POINTER1=
380 STA POINTER1 \POINTER2
390 CLC \***************
400 ADC #4 \ADD 4 TO
410 STA POINTER2 \POINTER1 AND
420 BCC SKIP \STORE IN
430 INC POINTER2+1 \POINTER2
440 .SKIP \***************
450 LDY #0 \OBTAIN ADDRESS
460 LDA (POINTER1),Y \AND LENGTH OF
470 STA string1 \EACH PAIR
480 LDA (POINTER2),Y \OF STRINGS
490 STA string2
500 INY
510 LDA (POINTER1),Y
520 STA string1+1
530 LDA (POINTER2),Y
540 STA string2+1
550 LDY #3
560 LDA (POINTER1),Y
570 STA length1
580 LDA (POINTER2),Y
590 STA length2
600 LDY #0 \***************
610 .COMPLOOP \COMPARE STRINGS
620 LDA (string2),Y \A CHARACTER AT
630 CMP (string1),Y \A TIME IF
640 BCC SWOP \NECESSARY
650 BNE NOSWOP
660 INY
670 CPY length1
680 BEQ NOSWOP
690 CPY length2
700 BEQ SWOP
710 BNE COMPLOOP
720 \*********************************
730 .STAGE \OUT OF RANGE
740 BNE OUTERLOOP \BRANCH PATCH
750 \*********************************
760 .SWOP
770 LDY #3
780 STY FLAG \SET SWOP FLAG
790 .SWOPLOOP \***************
800 LDA(POINTER1),Y \SWOP STRING
810 TAX \INFORMATION
820 LDA(POINTER2),Y \BLOCK A BYTE AT
830 STA(POINTER1),Y \A TIME(4 BYTES)
840 TXA
850 STA(POINTER2),Y
860 DEY
870 BPL SWOPLOOP
880 .NOSWOP \***************
890 INC CYCLE \INCREMENT
900 BNE SKIP2 \CYCLE
910 INC CYCLE+1
920 .SKIP2 \***************
930 LDA CYCLE \COMPARE CYCLE
940 CMP NUMBER \TO NUMBER
950 BNE INNERLOOP \IF <> BRANCH
960 LDA CYCLE+1 \TO INNERLOOP
970 CMP NUMBER+1
980 BNE INNERLOOP
990 LDA FLAG \IF SW.FLAG CLEAR
1000 BEQ FLAGCLEAR \BR. FLAGCLEAR
1010 LDA NUMBER \***************
1020 SEC \DECREMENT
1030 SBC #1 \NUMBER
1040 STA NUMBER
1050 BCS SKIP3
1060 DEC NUMBER+1
1070 .SKIP3
1080 LDA NUMBER \***************
1090 BNE STAGE \IF NUMBER <>0
1100 LDA NUMBER+1 \BRANCH OUTERLOOP
1110 BNE STAGE \VIA STAGE
1120 .FLAGCLEAR
1130 RTS:]
1140 NEXT PASS
1150
1160 REM BASIC IS FOR TESTING ONLY
1170 CLS
1180 MODE4
1190 INPUT"NUMBER OF STRINGS ",NUMBER%
1200 PRINT
1210 DIM ARRAY$(NUMBER%)
1220 FOR N%=1 TO NUMBER%
1230 string$=""
1240 FOR Z%=1 TO RND(10)
1250 K$=CHR$(RND(26)+64)
1260 string$=string$+K$
1270 NEXT Z%
1280 ARRAY$(N%)=string$
1290 PRINT ARRAY$(N%)
1300 NEXT N%
1310 PRINT
1320 PRINT "SORTING"
1330 PRINT
1340 START%=TIME
1350 CALL SORT,NUMBER%,ARRAY$(1)
1360 time%=TIME-START%
1370 FOR N%=1 TO NUMBER%
1380 PRINT ARRAY$(N%)
1390 NEXT
1400 PRINT:PRINT"NUMBER=";NUMBER%
1410 PRINT
1420 PRINT"SORTING TIME= ";time%/100;"
All that is now required is to explain the differences between Program 6.2 and Program 6.1. In this latter routine, POINTER1 and POINTER2 are the address pointers to the String Information Blocks of the pair of strings. A further level of indirect indexed addressing is necessary to pick up the actual string characters since the String Information Block supplies only the address of where the string is stored.
Lines 460-540 pick up the start addresses of the pair of strings, using indirect indexed addressing. The addresses are stored in string1 and string2 (zero-page locations).
Lines 550-590 pick up the fourth bytes of both the String Information Block and store them in length1 and length2 Line 600 sets the character counter to zero (Y register).
Lines 610-710 compare the ASCII codes of the pair of strings picked up by indirect indexed addressing. On comparison, as soon as the ASCII codes are found to be in descending order, the strings are immediately swopped. If the ASCII codes are found to be in ascending order, then no swop is required.
Line 660 increments the character counter.
Lines 670-680 compare the length of the first string (length1) to the character counter. If they are equal, no swop is required.
Lines 690-700 compare the length of the second string (length2) to the character counter. If they are equal, a swop is initiated.
Line 710 forces the branch to COMPLOOP which compares the next characters in the pair of strings, and so on.
Lines 730-740 are an out-of-range branch patch and, ideally, should not be there. It is due to the 128 byte displacement limit in relative addressing. This occurs in Line 1110.
Although the bubble sort routines given earlier are fast for small numbers of elements, the execution time increases alarmingly when in excess of about a hundred elements. To see the delay on high numbers, try running Program 6.1 with 1000 integers. You could well wait 45 seconds before the sort is completed. A far better solution is to use a merge sort algorithm. We noted earlier that the bubble sort is fairly efficient if only a small number of elements are to be sorted. We also noted that the use of a swop flag system significantly speeds up the execution of a bubble sort of a roughly ordered list. The merge sort algorithm takes advantage of both these virtues. Essentially, the array to be sorted is split up into small sets which are bubble sorted. These are merged to form larger sets which will be roughly in order. These larger sets are bubble sorted and merged to form even larger sets and so on until we are left with one large, roughly ordered list. This is finally bubble sorted, which will be efficient due to the points made earlier. A flowchart for a version of a merge sort is given in Fig. 6.4.
There is a danger of becoming intoxicated with verbosity in an attempt to explain the intricate details of a merge sort. A better grasp of the principles can be obtained by a Trace Table. In fact, any program which is difficult to follow will benefit from such an analysis. The idea is to follow the program through with arbitrary test data, keeping track of what happens to the various 'key' locations such as loop counters, etc. A Trace Table for the flowchart is given in Fig. 6.5. The unsorted array uses 8 random integers and shows how they would be sorted at various stages of the trace. Notice how the array becomes more and more ordered as each outer loop cycle is completed.
Fig. 6.4. Merge sort of an Integer array.
If the flowchart and trace table have been understood, Program 6.3 should be reasonably easy to decipher. In this program, there is provision for sorting signed integers. An expansion of Block 8 of the flowchart (Fig. 6.4) is given in Fig. 6.6, showing the extra details required.
TRACE TABLE FOR A MERGE SORT | |||
LOCATION LABELS | Value after 1st outer loop completed | Value after 2nd outer loop completed | Value after 3rd outer loop completed |
NUMBER | 8 | 8 | 8 |
POWER | 2 | 1 | 0 |
SIZE | 4 | 2 | 1 |
CYCLES | 4 | 6 | 7 |
Unsorted array | Array after 1st outer loop completed | Array after 2nd outer loop completed | Array after 3rd outer loop completed |
5 | 5 | 3 | 1 |
8 | 6 | 1 | 2 |
3 | 3 | 4 | 3 |
1 | 1 | 2 | 4 |
7 | 7 | 5 | 5 |
6 | 8 | 6 | 6 |
4 | 4 | 7 | 7 |
2 | 2 | 8 | 8 |
Fig 6.5. Simple Trace Table of merge sort algorithm.
Fig 6.6. Expansion of Block 8 in Fig. 6.4.
Program 6.3. Merge sort of an array of signed 32-bit integers
10 REM MERGE SORT OF ARRAY OF
20 REM SIGNED 32bit INTEGERS
30 NUMBER=&70:POINTER1=&72:POWER=&74
40 POINTER2=&75:SIZE=&77:LOOPCOUNT=&7
9:FLAG=&7B:STORE=&7C:CYCLES=&7E
50 DIM SORT 500
60 FOR PASS=0 TO 2 STEP 2
70 P%=SORT
80 [OPT PASS \***************
90 LDA &0601 \GET NUMBER OF
100 STA STORE \BASIC INTEGERS
110 LDA &0602 \IN ARRAY AND
120 STA STORE+1 \STORE IN NUMBER
130 LDY #0
140 STY SIZE+1
150 STY POWER \ALSO INITIALISE
160 LDA (STORE),Y \SIZE AND POWER
170 STA NUMBER
180 INY
190 STY SIZE
200 LDA (STORE),Y
210 STA NUMBER+1
220 .SIZELOOP \***************
230 INC POWER \FIND NEXT POWER
240 CLC \OF 2 >= NUMBER
250 ASL SIZE \STORE IN SIZE
260 ROL SIZE+1
270 SEC
280 LDA SIZE
290 SBC NUMBER
300 LDA SIZE+1
310 SBC NUMBER+1
320 BCC SIZELOOP
330 .OUTERLOOP \***************
340 CLC \DIVIDE SIZE
350 LSR SIZE+1 \BY 2
360 ROR SIZE
370 SEC \***************
380 LDA NUMBER \SUBTRACT SIZE
390 SBC SIZE \FROM NUMBER
400 STA CYCLES \STORE IN CYCLES
410 LDA NUMBER+1
420 SBC SIZE+1
430 STA CYCLES+1
440 .MIDLOOP \***************
450 LDA #0 \INITIALIE
460 STA FLAG \SWOP FLAG AND
470 STA LOOPCOUNT \LOOPCOUNT
480 STA LOOPCOUNT+1
490 LDA &0604 \***************
500 STA POINTER1 \STORE FIRST INT
510 LDA &0605 \ADDRESS IN
520 STA POINTER1+1 \POINTER1
530 LDA SIZE \***************
540 STA STORE \MULTIPLY SIZE
550 LDA SIZE+1 \BY 4 AND ADD
560 STA STORE+1 \ADD TO POINTER1
570 LDX #2 \STORE RESULT IN
580 .MULT4 \POINTER2
590 CLC
600 ASL STORE
610 ROL STORE+1
620 DEX
630 BNE MULT4
640 CLC
650 LDA POINTER1
660 ADC STORE
670 STA POINTER2
680 LDA POINTER1+1
690 ADC STORE+1
700 STA POINTER2+1
710 .INNERLOOP \***************
720 LDX #4 \SUBTRACT ONE
730 LDY #0 \INTEGER FROM
740 SEC \THE OTHER AND
750 .COMPLOOP \KEEP THE MOST
760 LDA (POINTER2),Y \SIGNIFICANT
770 SBC (POINTER1),Y \BYTE OF RESULT
780 INY \IN ACCUMULATOR
790 DEX \FOR SIGN BIT
800 BNE COMPLOOP
810 BVC NOOVERFLOW \REVERSE SIGN
820 EOR #&80 \BIT IF OVERFLOW
830 .NOOVERFLOW \OCCURS.
840 TAX \UPDATE N FLAG
850 BPL NOSWOP \N CLEAR,NOSWOP
860 DEY
870 STY FLAG
880 .SWOPLOOP \***************
890 LDA (POINTER1),Y \SWOP INTEGERS
900 TAX \A BYTE AT A
910 LDA (POINTER2),Y \TIME
920 STA (POINTER1),Y
930 TXA
940 STA (POINTER2),Y
950 DEY
960 BPL SWOPLOOP
970 BMI NOSWOP
980 \---------------------------------
990 .STAGE1 \OUT OF RANGE
1000 BNE MIDLOOP \BRANCH PATCHES
1010 .STAGE2
1020 BNE OUTERLOOP
1030 \---------------------------------
1040 .NOSWOP \***************
1050 INC LOOPCOUNT \INCREMENT
1060 BNE SKIP \LOOPCOUNT
1070 INC LOOPCOUNT+1
1080 .SKIP \***************
1090 LDA POINTER1 \ADD 4 TO
1100 CLC \POINTER1
1110 ADC #4
1120 STA POINTER1
1130 BCC SKIP2
1140 INC POINTER1+1
1150 .SKIP2 \***************
1160 LDA POINTER2 \ADD 4 TO
1170 CLC \POINTER2
1180 ADC #4
1190 STA POINTER2
1200 BCC SKIP3
1210 INC POINTER2+1
1220 .SKIP3 \***************
1230 LDA CYCLES \COMPARE
1240 CMP LOOPCOUNT \LOOPCOUNT
1250 BNE INNERLOOP \TO CYCLE
1260 LDA CYCLES+1 \IF <> BRANCH
1270 CMP LOOPCOUNT+1 \TO INNERLOOP
1280 BNE INNERLOOP
1290 LDA FLAG \IF SW.FLG CLEAR
1300 BEQ FLAGCLEAR \BR. FLAGCLEAR
1310 SEC
1320 LDA CYCLES \***************
1330 SBC #1 \DECREMENT
1340 STA CYCLES \CYCLES
1350 BCS SKIP4
1360 DEC CYCLES+1
1370 .SKIP4 \***************
1380 LDA CYCLES \IF CYCLES <>0
1390 BNE STAGE1 \THEN BRANCH
1400 LDA CYCLES+1 \TO MIDLOOP
1410 BNE STAGE1 \VIA STAGE1
1420 .FLAGCLEAR \***************
1430 DEC POWER \DECREMENT POWER
1440 BNE STAGE2 \IF>0 BR. STAGE2
1450 RTS:]
1460 NEXT PASS
1470
1480 REM BASIC TEST PROGRAM
1490 MODE4
1500 CLS
1510 INPUT"NUMBER OF INTEGERS ",NUMBER%
1520 PRINT
1530 DIM ARRAY%(NUMBER%)
1540 FOR N%=1 TO NUMBER%
1550 ARRAY%(N%)=RND/1000
1560 PRINT ARRAY%(N%)
1570 NEXT
1580 PRINT
1590 PRINT "SORTING"
1600 PRINT
1610 START%=TIME
1620 CALL SORT,NUMBER%,ARRAY%(1)
1630 time%=TIME-START%
1640 FOR N%=1 TO NUMBER%
1650 PRINT ARRAY%(N%)
1660 NEXT N%
1670 PRINT
1680 PRINT"NUMBER= ";NUMBER%
1690 PRINT
1700 PRINT"SORTING TIME= ";time%/100; "
SECONDS"
The program breakdown of Program 6.3 is as follows:
Lines 90-120 obtain the address of the BASIC variable NUMBER% from the CALL parameter block. The address is placed in zero-page locations STORE (2 bytes).
Lines 130-210 pick up the data by indirect indexed addressing and store it in NUMBER (zero-page). At the same time, various locations are initialised. Lines 220-320 are a block of code dedicated to finding the next power of 2, >= the contents of NUMBER. The result is stored in SIZE (2 bytes). The corresponding power index is stored in POWER (1 byte). The op-codes ASL and ROL in conjunction are convenient for 2-byte manipulation of powers of 2.
Lines 330-360 divide SIZE by 2 by shifting right.
Lines 370-430 subtract SIZE from NUMBER and store the result in CYCLES (2 bytes).
Lines 450-480 initialise LOOPCOUNT (2 bytes) and the swop FLAG to zero.
Lines 490-520 pick up the address of the first element in the array and store it in POINTER1 (2 bytes).
Lines 530-700 are a block of code which multiplies SIZE by 4 and adds POINTER1, storing the result in POINTER2. The reason why it is multiplied by 4 is because each integer occupies four bytes. The multiplication is achieved by shifting left twice. Line 720 sets the byte counter (X register) to 4.
Lines 730-800 subtract the two integers picked up by indirect indexed addressing, keeping the result of the most significant byte (which has the sign bit).
Line 810 checks if the V flag is set. If clear, it skips line 820.
Line 820 assumes that the V flag is set, so reverses the sign bit.
Line 840 updates the N flag to the accumulator contents. Tins is necessary because DEX, in fine 790, corrupts the N flag. T AX is economical for this purpose since it uses only 2 cycles.
Line 850 tests the sign of the accumulator and by-passes the swop loop if positive. This ensures that if both integers are the same, no swopping occurs.
Lines 890-960 swop the integers, a byte at a time, using indirect indexed addressing.
Line 970 serves no useful purpose in the program, other than causing a by-pass of the out of range branch-patch section (lines 990 1020).
Lines 1050-1080 increment LOOPCOUNT.
Lines 1090 1220 add the usual 4 to each of POINTER1 and POINTER2.
Lines 1230-1280 compare LOOPCOUNT to CYCLES, branching to INNER LOOP if not equal.
Lines 1290-1300 test the swop flag and, if clear, branch to FLAGCLEAR.
Lines 1310-1370 decrement CYCLES.
Lines 1380-1410 compare CYCLES to zero, branching to MID LOOP via STAGE1, the out of range branch-patch.
Lines 1430-1440 decrement POWER and compare to zero, branching to OUTERLOOP via STAGE2.
Lines 1480-1700 handle the BASIC test routine described earlier.
The overall structure of Program 6.4 is similar to Program 6.3, the only difference being the substitution of the string comparison routine (block 8 in the flowchart). This routine has already been described in detail for the bubble sort.
Program 6.4. Merge sort of a BASIC string array.
10 REM MERGE SORT OF STRING ARRAY
20 REM WITH VARIOUS LENGTH STRINGS
30 NUMBER=&70:POINTER1=&72:POWER=&74
40 POINTER2=&75:SIZE=&77:LOOPCOUNT=&7
9:FLAG=&7B:STORE=&7C:CYCLES=&7E
50 string1=&80:string2=&82:length1=&8
4:length2=&85
60 DIM SORT 500
70 FOR PASS=0 TO 2 STEP 2
80 P%=SORT
90 [OPT PASS \***************
100 LDA &0601 \GET NUMBER OF
110 STA STORE \BASIC INTEGERS
120 LDA &0602 \IN ARRAY AND
130 STA STORE+1 \STORE IN NUMBER
140 LDY #0
150 STY SIZE+1
160 STY POWER \ALSO INITIALISE
170 LDA (STORE),Y \SIZE AND POWER
180 STA NUMBER
190 INY
200 STY SIZE
210 LDA (STORE),Y
220 STA NUMBER+1
230 .SIZELOOP \***************
240 INC POWER \FIND NEXT POWER
250 CLC \OF 2 >= NUMBER
260 ASL SIZE \STORE IN SIZE
270 ROL SIZE+1
280 SEC
290 LDA SIZE
300 SBC NUMBER
310 LDA SIZE+1
320 SBC NUMBER+1
330 BCC SIZELOOP
340 .OUTERLOOP \***************
350 CLC \DIVIDE SIZE
360 LSR SIZE+1 \BY 2
370 ROR SIZE
380 SEC \***************
390 LDA NUMBER \SUBTRACT SIZE
400 SBC SIZE \FROM NUMBER
410 STA CYCLES \STORE IN CYCLES
420 LDA NUMBER+1
430 SBC SIZE+1
440 STA CYCLES+1
450 .MIDLOOP \***************
460 LDA #0 \INITIALIE
470 STA FLAG \SWOP FLAG AND
480 STA LOOPCOUNT \LOOPCOUNT
490 STA LOOPCOUNT+1
500 LDA &0604 \***************
510 STA POINTER1 \STORE FIRST INT
520 LDA &0605 \ADDRESS IN
530 STA POINTER1+1 \POINTER1
540 LDA SIZE \***************
550 STA STORE \MULTIPLY SIZE
560 LDA SIZE+1 \BY 4 AND ADD
570 STA STORE+1 \ADD TO POINTER1
580 LDX #2 \STORE RESULT IN
590 .MULT4 \POINTER2
600 CLC
610 ASL STORE
620 ROL STORE+1
630 DEX
640 BNE MULT4
650 CLC
660 LDA POINTER1
670 ADC STORE
680 STA POINTER2
690 LDA POINTER1+1
700 ADC STORE+1
710 STA POINTER2+1
720 .INNERLOOP \***************
730 LDY #0 \OBTAIN ADDRESS
740 LDA (POINTER1),Y \AND LENGTH
750 STA string1 \OF EACH OF
760 LDA (POINTER2),Y \PAIR OF STRINGS
770 STA string2
780 INY
790 LDA (POINTER1),Y
800 STA string1+1
810 LDA (POINTER2),Y
820 STA string2+1
830 LDY #3
840 LDA (POINTER1),Y
850 STA length1
860 LDA (POINTER2),Y
870 STA length2
880 LDY #0 \***************
890 .COMPLOOP \COMPARE STRINGS
900 LDA (string2),Y \A CHARACTER AT
910 CMP (string1),Y \A TIME IF
920 BCC SWOP \NECESSARY
930 BNE NOSWOP
940 INY
950 CPY length1
960 BEQ NOSWOP
970 CPY length2
980 BEQ SWOP
990 BNE COMPLOOP
1000 \---------------------------------
1010 .STAGE1 \OUT OF RANGE
1020 BNE MIDLOOP \BRANCH PATCHES
1030 .STAGE2
1040 BNE OUTERLOOP
1050 \---------------------------------
1060 .SWOP \***************
1070 LDY #3 \SET SWOP FLAG
1080 STY FLAG
1090 .SWOPLOOP \***************
1100 LDA (POINTER1),Y \SWOP STRING
1110 TAX \INFORMATION
1120 LDA (POINTER2),Y \BLOCK A BYTE AT
1130 STA (POINTER1),Y \A TIME(4 BYTES)
1140 TXA
1150 STA (POINTER2),Y
1160 DEY
1170 BPL SWOPLOOP
1180 .NOSWOP \***************
1190 INC LOOPCOUNT \INCREMENT
1200 BNE SKIP \LOOPCOUNT
1210 INC LOOPCOUNT+1
1220 .SKIP \***************
1230 LDA POINTER1 \ADD 4 TO
1240 CLC \POINTER1
1250 ADC #4
1260 STA POINTER1
1270 BCC SKIP2
1280 INC POINTER1+1
1290 .SKIP2 \***************
1300 LDA POINTER2 \ADD 4 TO
1310 CLC \POINTER2
1320 ADC #4
1330 STA POINTER2
1340 BCC SKIP3
1350 INC POINTER2+1
1360 .SKIP3 \***************
1370 LDA CYCLES \COMPARE
1380 CMP LOOPCOUNT \LOOPCOUNT
1390 BNE INNERLOOP \TO CYCLE
1400 LDA CYCLES+1 \IF <> BRANCH
1410 CMP LOOPCOUNT+1 \TO INNERLOOP
1420 BNE INNERLOOP
1430 LDA FLAG \IF SWAPFLG CLEAR
1440 BEQ FLAGCLEAR \BR. FLAGCLEAR
1450 SEC
1460 LDA CYCLES \***************
1470 SBC #1 \DECREMENT
1480 STA CYCLES \CYCLES
1490 BCS SKIP4
1500 DEC CYCLES+1
1510 .SKIP4 \***************
1520 LDA CYCLES \IF CYCLES <>0
1530 BNE STAGE1 \THEN BRANCH
1540 LDA CYCLES+1 \TO MIDLOOP
1550 BNE STAGE1 \VIA STAGE1
1560 .FLAGCLEAR \***************
1570 DEC POWER \DECREMENT POWER
1580 BNE STAGE2 \IF>0 BR. STAGE2
1590 RTS:]
1600 NEXT PASS
1620 REM BASIC TEST PROGRAM
1630 MODE4
1640 CLS
1650 INPUT"NUMBER OF STRINGS ",NUMBER%
1660 PRINT
1670 DIM ARRAY$(NUMBER%)
1680 FOR N%=1 TO NUMBER%
1690 string$=""
1700 FOR Z%=1 TO RND(10)
1710 K$=CHR$(RND(26)+64)
1720 string$=string$+K$
1730 NEXT Z%
1740 ARRAY$(N%)=string$
1750 PRINT ARRAY$(N%)
1760 NEXT N%
1770 PRINT
1780 PRINT "SORTING"
1790 PRINT
1800 START%=TIME
1810 CALL SORT,NUMBER%,ARRAY$(1)
1820 time%=TIME-START%
1830 FOR N%=1 TO NUMBER%
1840 PRINT ARRAY$(N%)
1850 NEXT N%
1860 PRINT
1870 PRINT"NUMBER= ";NUMBER%
1880 PRINT
1890 PRINT"SORTING TIME= ";time%/100; "
SECONDS"
Since the overall structure is similar to the previous program, a detailed line by line analysis is unnecessary.
Programs which handle words or tables often need to sort unsigned floating point numbers (most numerical values in such programs are unsigned). It is, therefore, important to have at least an outline understanding of how floating numbers are stored by the BASIC interpreter. A floating point number consists of a mantissa and an exponent. Four bytes are allocated to the mantissa and one byte for the exponent. The most significant bit of the exponent is the sign bit and is in reverse two's complement. That is to say, a negative exponent has '0' as the sign bit; a '1' indicates a positive exponent. The reason for this rather strange practice is that the maximum possible negative exponent closely approaches zero. This means that zero can be loosely taken as the most negative exponent. Therefore less negative exponents through to positive exponents correspond to a progression of increasingly larger exponents. From a mathematical viewpoint, a mantissa is always positive so no sign bit is required. Therefore, the sign bit in the mantissa is used to denote the sign of the entire number in conventional two's complement form.
Floating point variables are stored by the interpreter in a five-byte form, the details of which are below:
Fig. 6.7. Block 8 expansion for unsigned floating point merge sort
Block 8 of the flowchart in Fig. 6.4 is replaced by Fig. 6.7 . This is the only essential difference in the algorithm other than the addition of 5 instead of 4 to the address pointers POINTER1 and POINTER2 when appropriate. The complete listing is shown in Program 6.5 and requires the following BASIC parameters:
CALL SORT, NUMBER%, ARRAY(1)
The variables used are arbitrary but must be in the order given. The listing is liberaliy 'remarked' and, hopefully,. should require no further explanation.
Program 6.5. Merge sort of unsigned floating point array
10 REM MERGE SORT OF UNSIGNED
20 REM FLOATING POINT NUMBERS
30 NUMBER=&70:POINTER1=&72:POWER=&74
40 POINTER2=&75:SIZE=&77:LOOPCOUNT=&7
9:FLAG=&7B:STORE=&7C:CYCLES=&7E
50 DIM SORT 500
60 FOR PASS=0 TO 2 STEP 2
70 P%=SORT
80 [OPT PASS \***************
90 LDA &0601 \GET NUMBER OF
100 STA STORE \BASIC INTEGERS
110 LDA &0602 \IN ARRAY AND
120 STA STORE+1 \STORE IN NUMBER
130 LDY #0
140 STY SIZE+1
150 STY POWER \ALSO INITIALISE
160 LDA (STORE),Y \SIZE AND POWER
170 STA NUMBER
180 INY
190 STY SIZE
200 LDA (STORE),Y
210 STA NUMBER+1
220 .SIZELOOP \***************
230 INC POWER \FIND NEXT POWER
240 ASL SIZE \OF 2 >= NUMBER
250 ROL SIZE+1\AND STORE IN
260 SEC \SIZE
270 LDA SIZE
280 SBC NUMBER
290 LDA SIZE+1
300 SBC NUMBER+1
310 BCC SIZELOOP
320 .OUTERLOOP \***************
330 LSR SIZE+1 \DIVIDE SIZE
340 ROR SIZE \BY 2
350 SEC \***************
360 LDA NUMBER \SUBTRACT SIZE
370 SBC SIZE \FROM NUMBER
380 STA CYCLES \STORE IN CYCLES
390 LDA NUMBER+1
400 SBC SIZE+1
410 STA CYCLES+1
420 .MIDLOOP \***************
430 LDA #0 \INITIALIE
440 STA FLAG \SWOP FLAG AND
450 STA LOOPCOUNT \LOOPCOUNT
460 STA LOOPCOUNT+1
470 LDA &0604 \***************
480 STA POINTER1 \STORE FIRST INT
490 LDA &0605 \ADDRESS IN
500 STA POINTER1+1 \POINTER1
510 LDA SIZE+1 \***************
520 STA STORE+1 \MULTIPLY SIZE
530 LDA SIZE \BY 4 AND ADD
540 ASL A \SIZE THUS
550 ROL STORE+1 \OBTAINING AN
560 ASL A \EFFECTIVE
570 ROL STORE+1 \MULTIPLICATION
580 CLC \OF SIZE BY 5
590 ADC SIZE \STORE RESULT
600 ADC POINTER1 \IN POINTER2
610 STA POINTER2
620 LDA STORE+1
630 ADC SIZE+1
640 ADC POINTER1+1
650 STA POINTER2+1
740 .INNERLOOP \***************
750 LDY #0 \COMPARE
760 LDA (POINTER2),Y \EXPONENT OF
770 CMP (POINTER1),Y \PAIR OF FP
780 BCC SWOP \NUMBERS
790 BNE NOSWOP
800 LDY #4 \***************
810 SEC \SUBTRACT
820 .COMPLOOP \MANTISSI
830 LDA (POINTER2),Y \A BYTE AT A
840 SBC (POINTER1),Y \TIME KEEPING
850 DEYY \TRACK OF THE
860 BNE COMPLOOP \CARRY FLAG
870 BCS NOSWOP \AT COMPLETION
880 .SWOP \***************
890 LDY #4 \SET SWOP FLAG
900 STY FLAG
910 .SWOPLOOP \***************
920 LDA (POINTER1),Y \SWOP INTEGERS
930 TAX \A BYTE AT A
940 LDA (POINTER2),Y \TIME
950 STA (POINTER1),Y
960 TXA
970 STA (POINTER2),Y
980 DEY
990 BPL SWOPLOOP
1000 BMI NOSWOP
1010 \---------------------------------
1020 .STAGE1 \OUT OF RANGE
1030 BNE MIDLOOP \BRANCH PATCHES
1040 .STAGE2
1050 BNE OUTERLOOP
1060 \---------------------------------
1070 .NOSWOP \***************
1080 INC LOOPCOUNT \INCREMENT
1090 BNE SKIP \LOOPCOUNT
1100 INC LOOPCOUNT+1
1110 .SKIP \***************
1120 LDA POINTER1 \ADD 5 TO
1130 CLC \POINTER1
1140 ADC #5
1150 STA POINTER1
1160 BCC SKIP2
1170 INC POINTER1+1
1180 .SKIP2 \***************
1190 LDA POINTER2 \ADD 5 TO
1200 CLC \POINTER2
1210 ADC #5
1220 STA POINTER2
1230 BCC SKIP3
1240 INC POINTER2+1
1250 .SKIP3 \***************
1260 LDA CYCLES \COMPARE
1270 CMP LOOPCOUNT \LOOPCOUNT
1280 BNE INNERLOOP \TO CYCLE
1290 LDA CYCLES+1 \IF <> BRANCH
1300 CMP LOOPCOUNT+1 \TO INNERLOOP
1310 BNE INNERLOOP
1320 LDA FLAG \IF SWAPFLG CLEAR
1330 BEQ FLAGCLEAR \BR. FLAGCLEAR
1340 SEC
1350 LDA CYCLES \***************
1360 SBC #1 \DECREMENT
1370 STA CYCLES \CYCLES
1380 BCS SKIP4
1390 DEC CYCLES+1
1400 .SKIP4 \***************
1410 LDA CYCLES \IF CYCLES <>0
1420 BNE STAGE1 \THEN BRANCH
1430 LDA CYCLES+1 \TO MIDLOOP
1440 BNE STAGE1 \VIA STAGE1
1450 .FLAGCLEAR \***************
1460 DEC POWER \DECREMENT POWER
1470 BNE STAGE2 \IF>0 BR. STAGE2
1480 RTS:]
1490 NEXT PASS
1510 REM BASIC TEST PROGRAM
1520 MODE4
1530 CLS
1540 INPUT"NUMBER OF FP ELEMENTS ",NUMB
ER%
1550 PRINT
1560 DIM ARRAY(NUMBER%)
1570 FOR N%=1 TO NUMBER%
1580 ARRAY(N%)=ABS(RND)*1E-9
1590 PRINT ARRAY(N%)
1600 NEXT
1610 PRINT
1620 PRINT "SORTING"
1630 PRINT
1640 START%=TIME
1650 CALL SORT,NUMBER%,ARRAY(1)
1660 time%=TIME-START%
1670 FOR N%=1 TO NUMBER%
1680 PRINT ARRAY(N%)
1690 NEXT N%
1700 PRINT
1710 PRINT"SORTING TIME= ";time%/100; "
SECONDS"
1720 PRINT
1730 PRINT"NUMBER= ";NUMBER%
There are two common methods of generating multifield records in BASIC. One is to use fields of fixed length substrings where the whole record is stored as one string array element. The other is to create a two-dimensional string array where the records occupy one dimension and the fields occupy the other. This is often referred to as the row/column file format. Both have advantages and disadvantages. The former method is more economical when storing records since only one String Information block is set up per record by the interpreter. On the other hand, the BASIC programming can be tedious and expensive on memory. The latter method makes for concise programming in BASIC but is heavy on String Information blocks (the number of fields multiplied by the number of records). It is a matter of personal preference which method is used, so a machine code merge sort routine to handle each type of record format will be given. The requirement of any routine of this type is to sort entire records according to any specified field, therefore additional calling parameters will be necessary.
The complete source code listing and BASIC test routine are given in Program 6.6. The overall structure is similar to that of previous routines with the extra coding 'remarked' on the listing. The machine code call is executed from BASIC via the call statement:
CALL SORT, NUMBER%,FIELD%,FlELDEND%,ARRAY$(1)
where:
SORT the start address of the routine.
NUMBER%=the number of records in the array
FIELD%,=the first character position of the field in the string array element
FIELDEND%=the last character position of the field in the string array element.
ARRAY$(1)=the first usable element in the array.
By convention, the zero element is reserved for headings, labels, etc.
Program 6.6. Merge sort of multifield fixed length records.
10 REM MERGE SORT OF MULTIFIELD
20 REM FIXED LENGTH RECORDS
30 NUMBER=&70:POINTER1=&72:POWER=&74
40 POINTER2=&75:SIZE=&77:LOOPCOUNT=&7
9:FLAG=&7B:STORE=&7C:CYCLES=&7E
50 string1=&80:string2=&82:FIELD=&84:
FIELDEND=&85
60 DIM SORT 500
70 FOR PASS=0 TO 2 STEP 2
80 P%=SORT
90 [OPT PASS \***************
100 LDA &0601 \GET NUMBER OF
110 STA STORE \RECORDS IN THE
120 LDA &0602 \BASIC ARRAY AND
130 STA STORE+1 \STORE IN NUMBER
140 LDY #0
150 STY SIZE+1
160 STY POWER \ALSO INITIALISE
170 LDA (STORE),Y \SIZE AND POWER
180 STA NUMBER
190 INY
200 STY SIZE
210 LDA (STORE),Y
220 STA NUMBER+1
230 LDA &0604 \***************
240 STA STORE \STORE FIELD
250 LDA &0605 \START POSITION
260 STA STORE+1 \IN FIELD
270 DEY
280 LDA (STORE),Y
290 STA FIELD
300 LDA &0607 \***************
310 STA STORE \STORE FIELD
320 LDA &0608 \END POSITION
330 STA STORE+1 \IN FIELDEND
340 LDA (STORE),Y
350 STA FIELDEND
360 .SIZELOOP \***************
370 INC POWER \FIND NEXT POWER
380 CLC \OF 2 >= NUMBER
390 ASL SIZE \STORE IN SIZE
400 ROL SIZE+1
410 SEC
420 LDA SIZE
430 SBC NUMBER
440 LDA SIZE+1
450 SBC NUMBER+1
460 BCC SIZELOOP
470 .OUTERLOOP \***************
480 CLC \DIVIDE SIZE
490 LSR SIZE+1 \BY 2
500 ROR SIZE
510 SEC \***************
520 LDA NUMBER \SUBTRACT SIZE
530 SBC SIZE \FROM NUMBER
540 STA CYCLES \STORE IN CYCLES
550 LDA NUMBER+1
560 SBC SIZE+1
570 STA CYCLES+1
580 .MIDLOOP \***************
590 LDA #0 \SET SWOP FLAG
600 STA FLAG \AND LOOPCOUNT
610 STA LOOPCOUNT \TO ZERO
620 STA LOOPCOUNT+1 \***************
630 LDA &060A \STORE START
640 STA POINTER1 \ADDRESS OF
650 LDA &060B \ $ INF.BLOCK IN
660 STA POINTER1+1 \POINTER1
670 LDA SIZE \***************
680 STA STORE \MULTIPLY SIZE
690 LDA SIZE+1 \BY 4 AND ADD
700 STA STORE+1 \ADD TO POINTER1
710 LDX #2 \STORE RESULT IN
720 .MULT4 \POINTER2
730 CLC
740 ASL STORE
750 ROL STORE+1
760 DEX
770 BNE MULT4
780 CLC
790 LDA POINTER1
800 ADC STORE
810 STA POINTER2
820 LDA POINTER1+1
830 ADC STORE+1
840 STA POINTER2+1
850 .INNERLOOP \***************
860 LDY #0 \OBTAIN ADDRESS
870 LDA (POINTER1),Y \AND LENGTH
880 STA string1 \OF EACH OF
890 LDA (POINTER2),Y \PAIR OF STRINGS
900 STA string2
910 INY
920 LDA (POINTER1),Y
930 STA string1+1
940 LDA (POINTER2),Y
950 STA string2+1
960 LDY FIELD \INIT.Yreg FIELD
970 DEY
980 .COMPLOOP \COMPARE FIELDS
990 LDA (string2),Y \A CHARACTER AT
1000 CMP (string1),Y \A TIME IF
1010 BCC SWOP \IF NECESSARY
1020 BNE NOSWOP
1030 INY
1040 CPY FIELDEND
1050 BNE COMPLOOP
1060 BEQ NOSWOP
1070 \---------------------------------
1080 .STAGE1 \OUT OF RANGE
1090 BNE MIDLOOP \BRANCH PATCHES
1100 .STAGE2
1110 BNE OUTERLOOP
1120 \---------------------------------
1130 .SWOP \***************
1140 LDY #3 \SET SWOP FLAG
1150 STY FLAG
1160 .SWOPLOOP \***************
1170 LDA (POINTER1),Y \SWOP STRING
1180 TAX \INFORMATION
1190 LDA (POINTER2),Y \BLOCK A BYTE AT
1200 STA (POINTER1),Y \A TIME(4 BYTES)
1210 TXA
1220 STA (POINTER2),Y
1230 DEY
1240 BPL SWOPLOOP
1250 .NOSWOP \***************
1260 INC LOOPCOUNT \INCREMENT
1270 BNE SKIP \LOOPCOUNT
1280 INC LOOPCOUNT+1
1290 .SKIP \***************
1300 LDA POINTER1 \ADD 4 TO
1310 CLC \POINTER1
1320 ADC #4
1330 STA POINTER1
1340 BCC SKIP2
1350 INC POINTER1+1
1360 .SKIP2 \***************
1370 LDA POINTER2 \ADD 4 TO
1380 CLC \POINTER2
1390 ADC #4
1400 STA POINTER2
1410 BCC SKIP3
1420 INC POINTER2+1
1430 .SKIP3 \***************
1440 LDA CYCLES \COMPARE
1450 CMP LOOPCOUNT \LOOPCOUNT
1460 BNE INNERLOOP \TO CYCLE
1470 LDA CYCLES+1 \IF <> BRANCH
1480 CMP LOOPCOUNT+1 \TO INNERLOOP
1490 BNE INNERLOOP
1500 LDA FLAG \IF SWAPFLG CLEAR
1510 BEQ FLAGCLEAR \BR. FLAGCLEAR
1520 SEC
1530 LDA CYCLES \***************
1540 SBC #1 \DECREMENT
1550 STA CYCLES \CYCLES
1560 BCS SKIP4
1570 DEC CYCLES+1
1580 .SKIP4 \***************
1590 LDA CYCLES \IF CYCLES <>0
1600 BNE STAGE1 \THEN BRANCH
1610 LDA CYCLES+1 \TO MIDLOOP
1620 BNE STAGE1 \VIA STAGE1
1630 .FLAGCLEAR \***************
1640 DEC POWER \DECREMENT POWER
1650 BNE STAGE2 \IF>0 BR. STAGE2
1660 RTS:]
1670 NEXT PASS
1690 REM BASIC TEST PROGRAM
1700 MODE4
1710 CLS
1720 INPUT"NUMBER OF STRINGS ",NUMBER%
1730 DIM ARRAY$(NUMBER%)
1740 FOR N%=1 TO NUMBER%
1750 string$=""
1760 FOR Z%=1 TO 10
1770 K$=CHR$(RND(26)+64)
1780 string$=string$+K$
1790 NEXT Z%
1800 ARRAY$(N%)=string$
1810 PRINT ARRAY$(N%)
1820 NEXT N%
1830 INPUT"GIVE FIELD START POS. ",FIE
LD%
1840 INPUT"GIVE FIELD END POS. ",FIE
LDEND%
1850 PRINT "SORTING"
1860 START%=TIME
1870 CALL SORT,NUMBER%,FIELD%,FIELDEND%
,ARRAY$(1)
1880 time%=TIME-START%
1890 FOR N%=1 TO NUMBER%
1900 PRINT ARRAY$(N%)
1910 NEXT N%
1920 PRINT"SORTED FIELD BEGINS AT CHARA
CTER ";FIELD%
1930 PRINT"SORTED FIELD ENDS WITH CHARA
CTER ";FIELDEND%
1940 PRINT"NUMBER OF RECORDS= ";NUMBER%
1950 PRINT"SORTING TIME= ";time%/100; "
SECONDS"
The interpreter stores the String Information blocks corresponding to multidimensional string array elements sequentially in memory. The following series shows the order in which they occur for a two-dimensional string array:
A$(0,0), A$(0,1), A$(0,2), A$(1,0), A$(1,1), A$(1,2)......A$(R,C)
If a file is DIMensioned in BASIC:
ARRAY$(ROWNUM%,COLNUM%)
then a file ARRAY$ can be considered as containing ROWNUM% records and COLNUM% fields. We can define a specific field of a specific record by:
ARRAY$(RECORD%,FlELD%)
If we call the sort routine with
CALL SORT,ROWNUM%,COLNUM%,FIELD%,ARRAY(1,0)
all the necessary parameters required to sort all the records by field are passed. The complete source code listing and BASIC test routine are shown in Program 6.7
Since each String Information block occupies four bytes and there are COLNUM%+1 fields to each record, the sort routine will need to calculate the number of bytes necessary before swopping the SI blocks corresponding to each record. This is performed by lines 380 to 480 and the result is stored in NUMBYTE (1 byte),
The by now familar SI block address pointers POINTER1 and POINTER2 refer to the zeroth dimension of COLNUM% so an offset needs to be calculated by the routine to point to the required sort field element SI block in the COLNUN% dimension (remember that 4 bytes offset is required for each). This is performed by lines 490 to 560 and the result is stored in offset (1 byte). Using indirect indexed addressing, the offset accesses the required field SI block position. Plainly, we will need to add NUMBYTE instead of 4 to the previous SI block address pointers in order to access the next record. Apart from these differences, the overall structure is similar to that previously described.
The routine can sort records with up to a maximum of 128/4=32 fields (not much of a handicap in practice). Program 6.7 has been well-tried and tested in a practical filing system and will sort a computer full or records in less than a second.
Program 6.7. Merge sort of a two-dimensional string array
10 REM MERGE SORT OF A TWO
20 REM DIMENSIONAL STRING ARRAY
30 REM row/column record format
40 REM sorting entire record (row)
50 REM according to any specified
60 REM field (column)
70 NUMBER=&70:POINTER1=&72:POWER=&74
80 POINTER2=&75:SIZE=&77:LOOPCOUNT=&7
9:FLAG=&7B:STORE=&7C:CYCLES=&7E
90 string1=&80:string2=&82:length1=&8
4:length2=&85:NUMBYTE=&86:offset=&87
100 DIM SORT 500
110 FOR PASS=0 TO 2 STEP 2
120 P%=SORT
130 [OPT PASS \***************
140 LDA &0601 \GET NUMBER OF
150 STA STORE \BASIC STRINGS
160 LDA &0602 \IN ARRAY AND
170 STA STORE+1 \STORE IN NUMBER
180 LDY #0
190 STY SIZE+1
200 STY POWER \ALSO INITIALISE
210 LDA (STORE),Y \SIZE AND POWER
220 STA NUMBER
230 INY
240 STY SIZE
250 LDA (STORE),Y
260 STA NUMBER+1
270 .SIZELOOP \***************
280 INC POWER \FIND NEXT POWER
290 CLC \OF 2 >= NUMBER
300 ASL SIZE \STORE IN SIZE
310 ROL SIZE+1
320 SEC
330 LDA SIZE
340 SBC NUMBER
350 LDA SIZE+1
360 SBC NUMBER+1
370 BCC SIZELOOP
380 LDA &604 \***************
390 STA STORE \GET NUMBER OF
400 LDA &605 \FIELDS IN
410 STA STORE+1 \RECORD THEN
420 LDY #0 \ADD 1 AND
430 LDA (STORE),Y \MULTIPLY BY 4
440 CLC \STORE RESULT
450 ADC #1 \IN NUMBYTE
460 ASL A
470 ASL A
480 STA NUMBYTE \***************
490 LDA &0607 \GET SORT FIELD
500 STA STORE \NUMBER THEN
510 LDA &0608 \MULTIPLY BY 4
520 STA STORE+1 \STORE RESULT IN
530 LDA (STORE),Y \offset
540 ASL A
550 ASL A
560 STA offset
570 .OUTERLOOP \***************
580 CLC \DIVIDE SIZE
590 LSR SIZE+1 \BY 2
600 ROR SIZE
610 SEC \***************
620 LDA NUMBER \SUBTRACT SIZE
630 SBC SIZE \FROM NUMBER
640 STA CYCLES \STORE IN CYCLES
650 LDA NUMBER+1
660 SBC SIZE+1
670 STA CYCLES+1
680 .MIDLOOP \***************
690 LDA #0 \SET SWOP FLAG
700 STA FLAG \AND LOOPCOUNT
710 STA LOOPCOUNT \TO ZERO
720 STA LOOPCOUNT+1 \***************
730 LDA &060A \STORE START
740 STA POINTER1 \ADDRESS OF
750 LDA &060B \ $ INF.BLOCK IN
760 STA POINTER1+1 \POINTER1
770 LDA #0 \***************
780 STA STORE \MULTIPLY SIZE
790 STA STORE+1 \BY NUMBYTE
800 LDX NUMBYTE \AND ADD TO
810 .MULTLOOP \POINTER1
820 CLC \STORE RESULT IN
830 LDA STORE \POINTER2
840 ADC SIZE
850 STA STORE
860 LDA STORE+1
870 STA SIZE+1
880 STA STORE+1
890 DEX
900 BNE MULTLOOP
910 CLC
920 LDA POINTER1
930 ADC STORE
940 STA POINTER2
950 LDA POINTER1+1
960 ADC STORE+1
970 STA POINTER2+1
980 .INNERLOOP \***************
990 LDY offset \OBTAIN ADDRESS
1000 LDA (POINTER1),Y \AND LENGTH
1010 STA string1 \OF EACH OF
1020 LDA (POINTER2),Y \PAIR OF STRINGS
1030 STA string2
1040 INY
1050 LDA (POINTER1),Y
1060 STA string1+1
1070 LDA (POINTER2),Y
1080 STA string2+1
1090 INY
1100 INY
1110 LDA (POINTER1),Y
1120 STA length1
1130 LDA (POINTER2),Y
1140 STA length2
1150 LDY #0 \***************
1160 .COMPLOOP \COMPARE FIELDS
1170 LDA (string2),Y \A CHARACTER AT
1180 CMP (string1),Y \A TIME IF
1190 BCC SWOP \IF NECESSARY
1200 BNE NOSWOP
1210 INY
1220 CPY length1
1230 BEQ NOSWOP
1240 CPY length2
1250 BEQ SWOP
1260 BNE COMPLOOP
1270 \---------------------------------
1280 .STAGE1 \OUT OF RANGE
1290 BNE MIDLOOP \BRANCH PATCHES
1300 .STAGE2
1310 BNE OUTERLOOP
1320 \---------------------------------
1330 .SWOP \INITIALISE BYTE
1340 LDY NUMBYTE \COUNTER TO
1350 DEY \NUMBYTE
1360 STY FLAG \SET SWOP FLAG
1370 .SWOPLOOP \***************
1380 LDA (POINTER1),Y \SWOP STRING
1390 TAX \INFORMATION
1400 LDA (POINTER2),Y \BLOCK A BYTE AT
1410 STA (POINTER1),Y \A TIME TILL
1420 TXA \COMPLETE RECORD
1430 STA (POINTER2),Y \IS SWOPPED
1440 DEY
1450 BPL SWOPLOOP
1460 .NOSWOP \***************
1470 INC LOOPCOUNT \INCREMENT
1480 BNE SKIP \LOOPCOUNT
1490 INC LOOPCOUNT+1
1500 .SKIP \***************
1510 LDA POINTER1 \ADD NUMBYTE TO
1520 CLC \POINTER1
1530 ADC NUMBYTE
1540 STA POINTER1
1550 BCC SKIP2
1560 INC POINTER1+1
1570 .SKIP2 \***************
1580 LDA POINTER2 \ADD NUMBYTE TO
1590 CLC \POINTER2
1600 ADC NUMBYTE
1610 STA POINTER2
1620 BCC SKIP3
1630 INC POINTER2+1
1640 .SKIP3 \***************
1650 LDA CYCLES \COMPARE
1660 CMP LOOPCOUNT \LOOPCOUNT
1670 BNE INNERLOOP \TO CYCLE
1680 LDA CYCLES+1 \IF <> BRANCH
1690 CMP LOOPCOUNT+1 \TO INNERLOOP
1700 BNE INNERLOOP
1710 LDA FLAG \IF SWAPFLG CLEAR
1720 BEQ FLAGCLEAR \BR. FLAGCLEAR
1730 SEC
1740 LDA CYCLES \***************
1750 SBC #1 \DECREMENT
1760 STA CYCLES \CYCLES
1770 BCS SKIP4
1780 DEC CYCLES+1
1790 .SKIP4 \***************
1800 LDA CYCLES \IF CYCLES <>0
1810 BNE STAGE1 \THEN BRANCH
1820 LDA CYCLES+1 \TO MIDLOOP
1830 BNE STAGE1 \VIA STAGE1
1840 .FLAGCLEAR \***************
1850 DEC POWER \DECREMENT POWER
1860 BNE STAGE2 \IF>0 BR. STAGE2
1870 RTS:]
1880 NEXT PASS
1900 REM BASIC TEST PROGRAM
1910 MODE4
1920 CLS
1930 INPUT"NUMBER OF RECORDS ",ROWNUM%
1940 INPUT"NUMBER OF COLUMNS ",COLNUM%
1950 INPUT"SORT WHICH FIELD ",FIELD%
1960 PRINT
1970 DIM ARRAY$(ROWNUM%,COLNUM%)
1980 FOR R%=1 TO ROWNUM%
1990 FOR C%=0 TO COLNUM%-1
2000 string$=""
2010 FOR Z%=1 TO RND(10)
2020 K$=CHR$(RND(26)+64)
2030 string$=string$+K$
2040 NEXT Z%
2050 ARRAY$(R%,C%)=string$
2060 PRINT ARRAY$(R%,C%)
2070 NEXT C%
2080 PRINT
2090 NEXT R%
2100 PRINT "SORTING"
2110 PRINT
2120 START%=TIME
2130 CALL SORT,ROWNUM%,COLNUM%,FIELD%,A
RRAY$(1,0)
2140 time%=TIME-START%
2150 FOR R%=1 TO ROWNUM%
2160 FOR C%=0 TO COLNUM%-1
2170 PRINT ARRAY$(R%,C%)
2180 NEXT C%
2190 PRINT
2200 NEXT R%
2210 PRINT
2220 PRINT"RECORDS= ";ROWNUM%
2230 PRINT
2240 PRINT"SORTING TIME= ";time%/100; "
SECONDS"
As a guide to the execution times you can expect from the sorting routines, a comprehensive table is given below for various array sizes.
Table 6.1: Table of sorting times.
Unsigned integer bubble sort | |||||
Number of elements | 100 | 300 | 1000 | 2000 | 3000 |
Time (secs) reverse order | 0.7 | 5.7 | 64 | 253 | 567 |
Time (secs) random (average) | 0.5 | 4.3 | 47 | 187 | 418 |
String bubble sort | |||||
Number of elements | 100 | 300 | 1000 | ||
Time (secs) random length strings | 0.5 | 4.3 | 50 | ||
Signed integer merge sort | |||||
Number of elements | 100 | 300 | 1000 | 2000 | 3000 |
Time (secs) reverse order | 0.09 | 0.3 | 1.4 | 3 | 5 |
Time (secs) random (average) | 0.3 | 1.2 | 8.5 | 22 | 47 |
String merge sort | |||||
Number of elements | 100 | 300 | 1000 | ||
Time (secs) random length strings | 0.2 | 1.2 | 8.5 | ||
Unsigned floating point merge sort | |||||
Number of elements | 100 | 300 | 1000 | 2000 | |
Time (secs) random (average) | 0.2 | 1.2 | 8.0 | 24 | |
Multi-field fixed length records | |||||
Number of records | 100 | 200 | 300 | ||
Time (secs) random | 0.2 | 0.7 | 1.2 | ||
Multi-field unlimited length records (2-dimensional array) | |||||
Number of records 100 | 200 | 300 | |||
Time (secs) 3-field records | 0.3 | 1.2 | 1.7 |