Home » Archimedes archive » Micro User » MU 1990-02.adf » TreeSrt
TreeSrt
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » Archimedes archive » Micro User » MU 1990-02.adf |
| Filename: | TreeSrt |
| Read OK: | ✔ |
| File size: | 0626 bytes |
| Load address: | FFFFFB42 |
| Exec address: | 181D0E0D |
Duplicates
There are 2 duplicate copies of this file in the archive:
- Archimedes archive » Micro User » MU 1990-02.adf » TreeSrt
- AEW website » mu » mu_5_25_discs_Micro_User_07_12_D-MU07_12.ssd » TreeSrt
- AEW website » mu » mu_Micro_User_07_12_MU7-12_B.uef » TreeSrt
File contents
10REM > TreeSort
20REM by Anton L. Mans
30REM (c) The Micro User
40number_of_words%=10
50left%=0:right%=1:DIM word$(number_of_words%),pointer%(number_of_words%,1)
60MODE 0
70PROCrandom_words
80TIME=0
90PROCsetup_tree
100T%=TIME
110PROCprint_unsorted
120VDU 28,40,31,79,0
130PRINT ''SPC9;"SORTED LIST"'SPC9;STRING$(11,"-")
140PROCprint_sorted(1)
150VDU26
160PRINT TAB(20,30)"Time to sort ";number_of_words%;" words: ";T%/100;" seconds.";
170VDU 26
180END
190DEF PROCsetup_tree LOCAL I%
200CLS
210PRINT TAB(36,10);"Sorting."
220FOR I%=2 TO number_of_words%
230IF word$(I%)<=word$(1) THEN PROCleft(1) ELSE PROCright(1)
240NEXT
250ENDPROC
260DEF PROCleft(node%)
270IF pointer%(node%,left%)=0 THEN pointer%(node%,left%)=I%:ENDPROC
280IF word$(pointer%(node%,left%))>=word$(I%) THEN PROCleft(pointer%(node%,left%)) ELSE PROCright(pointer%(node%,left%))
290ENDPROC
300DEF PROCright(node%)
310IF pointer%(node%,right%)=0 THEN pointer%(node%,right%)=I%:ENDPROC
320IF word$(pointer%(node%,right%))>=word$(I%) THEN PROCleft(pointer%(node%,right%)) ELSE PROCright(pointer%(node%,right%))
330ENDPROC
340DEF PROCprint_sorted(I%):IF I%=0 THEN ENDPROC
350LOCAL @%:@%=&902
360PROCprint_sorted(pointer%(I%,left%))
370PRINT SPC6;word$(I%);TAB(18);" (",I%;")"
380PROCprint_sorted(pointer%(I%,right%))
390ENDPROC
400DEF PROCprint_unsorted LOCAL @%,I%
410@%=&905
420CLS
430PRINT'SPC7;"WORD";SPC(12);"POINTERS"
440PRINT SPC22;"left right"
450PRINT SPC3;STRING$(28,"-")
460FOR I%=1 TO number_of_words%
470PRINT,I%,TAB(6)word$(I%),TAB(20),pointer%(I%,0),pointer%(I%,1)
480NEXT
490ENDPROC
500DEF PROCrandom_words LOCAL I%,J%
510PRINT TAB(20,10);"Setting up array of random words."
520FOR I%=1 TO number_of_words%
530word$(I%)="1234567890"
540word$(I%)=""
550FOR J%=1 TO RND(5)+5
560word$(I%)=word$(I%)+CHR$(64+RND(26))
570NEXT
580pointer%(I%,0)=0
590pointer%(I%,1)=0
600NEXT
610ENDPROC
620NEXT
630ENDPROC
� > TreeSort
� by Anton L. Mans
� (c) The Micro User
(number_of_words%=10
2Kleft%=0:right%=1:� word$(number_of_words%),pointer%(number_of_words%,1)
<� 0
F�random_words
P�=0
Z�setup_tree
dT%=�
n�print_unsorted
x� 28,40,31,79,0
�$� ''�9;"SORTED LIST"'�9;�11,"-")
��print_sorted(1)
��26
�L� �20,30)"Time to sort ";number_of_words%;" words: ";T%/100;" seconds.";
�� 26
��
�� �setup_tree � I%
��
�� �36,10);"Sorting."
� � I%=2 � number_of_words%
�0� word$(I%)<=word$(1) � �left(1) � �right(1)
��
��
� �left(node%)
:� pointer%(node%,left%)=0 � pointer%(node%,left%)=I%:�
l� word$(pointer%(node%,left%))>=word$(I%) � �left(pointer%(node%,left%)) � �right(pointer%(node%,left%))
"�
,� �right(node%)
6<� pointer%(node%,right%)=0 � pointer%(node%,right%)=I%:�
@o� word$(pointer%(node%,right%))>=word$(I%) � �left(pointer%(node%,right%)) � �right(pointer%(node%,right%))
J�
T"� �print_sorted(I%):� I%=0 � �
^� @%:@%=&902
h%�print_sorted(pointer%(I%,left%))
r#� �6;word$(I%);�18);" (",I%;")"
|&�print_sorted(pointer%(I%,right%))
��
� � �print_unsorted � @%,I%
� @%=&905
��
� �'�7;"WORD";�(12);"POINTERS"
�� �22;"left right"
�� �3;�28,"-")
� � I%=1 � number_of_words%
�8�,I%,�6)word$(I%),�20),pointer%(I%,0),pointer%(I%,1)
��
��
�� �random_words � I%,J%
�1� �20,10);"Setting up array of random words."
� I%=1 � number_of_words%
word$(I%)="1234567890"
word$(I%)=""
&� J%=1 � �(5)+5
0#word$(I%)=word$(I%)+�(64+�(26))
:�
Dpointer%(I%,0)=0
Npointer%(I%,1)=0
X�
b�
l�
v�
� 00000000 0d 00 0a 10 f4 20 3e 20 54 72 65 65 53 6f 72 74 |..... > TreeSort|
00000010 0d 00 14 18 f4 20 20 20 62 79 20 41 6e 74 6f 6e |..... by Anton|
00000020 20 4c 2e 20 4d 61 6e 73 0d 00 1e 1a f4 20 20 20 | L. Mans..... |
00000030 28 63 29 20 54 68 65 20 4d 69 63 72 6f 20 55 73 |(c) The Micro Us|
00000040 65 72 0d 00 28 17 6e 75 6d 62 65 72 5f 6f 66 5f |er..(.number_of_|
00000050 77 6f 72 64 73 25 3d 31 30 0d 00 32 4b 6c 65 66 |words%=10..2Klef|
00000060 74 25 3d 30 3a 72 69 67 68 74 25 3d 31 3a de 20 |t%=0:right%=1:. |
00000070 77 6f 72 64 24 28 6e 75 6d 62 65 72 5f 6f 66 5f |word$(number_of_|
00000080 77 6f 72 64 73 25 29 2c 70 6f 69 6e 74 65 72 25 |words%),pointer%|
00000090 28 6e 75 6d 62 65 72 5f 6f 66 5f 77 6f 72 64 73 |(number_of_words|
000000a0 25 2c 31 29 0d 00 3c 07 eb 20 30 0d 00 46 11 f2 |%,1)..<.. 0..F..|
000000b0 72 61 6e 64 6f 6d 5f 77 6f 72 64 73 0d 00 50 07 |random_words..P.|
000000c0 d1 3d 30 0d 00 5a 0f f2 73 65 74 75 70 5f 74 72 |.=0..Z..setup_tr|
000000d0 65 65 0d 00 64 08 54 25 3d 91 0d 00 6e 13 f2 70 |ee..d.T%=...n..p|
000000e0 72 69 6e 74 5f 75 6e 73 6f 72 74 65 64 0d 00 78 |rint_unsorted..x|
000000f0 13 ef 20 32 38 2c 34 30 2c 33 31 2c 37 39 2c 30 |.. 28,40,31,79,0|
00000100 0d 00 82 24 f1 20 27 27 89 39 3b 22 53 4f 52 54 |...$. ''.9;"SORT|
00000110 45 44 20 4c 49 53 54 22 27 89 39 3b c4 31 31 2c |ED LIST"'.9;.11,|
00000120 22 2d 22 29 0d 00 8c 14 f2 70 72 69 6e 74 5f 73 |"-").....print_s|
00000130 6f 72 74 65 64 28 31 29 0d 00 96 07 ef 32 36 0d |orted(1).....26.|
00000140 00 a0 4c f1 20 8a 32 30 2c 33 30 29 22 54 69 6d |..L. .20,30)"Tim|
00000150 65 20 74 6f 20 73 6f 72 74 20 22 3b 6e 75 6d 62 |e to sort ";numb|
00000160 65 72 5f 6f 66 5f 77 6f 72 64 73 25 3b 22 20 77 |er_of_words%;" w|
00000170 6f 72 64 73 3a 20 22 3b 54 25 2f 31 30 30 3b 22 |ords: ";T%/100;"|
00000180 20 73 65 63 6f 6e 64 73 2e 22 3b 0d 00 aa 08 ef | seconds.";.....|
00000190 20 32 36 0d 00 b4 05 e0 0d 00 be 16 dd 20 f2 73 | 26.......... .s|
000001a0 65 74 75 70 5f 74 72 65 65 20 ea 20 49 25 0d 00 |etup_tree . I%..|
000001b0 c8 05 db 0d 00 d2 18 f1 20 8a 33 36 2c 31 30 29 |........ .36,10)|
000001c0 3b 22 53 6f 72 74 69 6e 67 2e 22 0d 00 dc 1d e3 |;"Sorting.".....|
000001d0 20 49 25 3d 32 20 b8 20 6e 75 6d 62 65 72 5f 6f | I%=2 . number_o|
000001e0 66 5f 77 6f 72 64 73 25 0d 00 e6 30 e7 20 77 6f |f_words%...0. wo|
000001f0 72 64 24 28 49 25 29 3c 3d 77 6f 72 64 24 28 31 |rd$(I%)<=word$(1|
00000200 29 20 8c 20 f2 6c 65 66 74 28 31 29 20 8b 20 f2 |) . .left(1) . .|
00000210 72 69 67 68 74 28 31 29 0d 00 f0 05 ed 0d 00 fa |right(1)........|
00000220 05 e1 0d 01 04 12 dd 20 f2 6c 65 66 74 28 6e 6f |....... .left(no|
00000230 64 65 25 29 0d 01 0e 3a e7 20 70 6f 69 6e 74 65 |de%)...:. pointe|
00000240 72 25 28 6e 6f 64 65 25 2c 6c 65 66 74 25 29 3d |r%(node%,left%)=|
00000250 30 20 8c 20 70 6f 69 6e 74 65 72 25 28 6e 6f 64 |0 . pointer%(nod|
00000260 65 25 2c 6c 65 66 74 25 29 3d 49 25 3a e1 0d 01 |e%,left%)=I%:...|
00000270 18 6c e7 20 77 6f 72 64 24 28 70 6f 69 6e 74 65 |.l. word$(pointe|
00000280 72 25 28 6e 6f 64 65 25 2c 6c 65 66 74 25 29 29 |r%(node%,left%))|
00000290 3e 3d 77 6f 72 64 24 28 49 25 29 20 8c 20 f2 6c |>=word$(I%) . .l|
000002a0 65 66 74 28 70 6f 69 6e 74 65 72 25 28 6e 6f 64 |eft(pointer%(nod|
000002b0 65 25 2c 6c 65 66 74 25 29 29 20 8b 20 f2 72 69 |e%,left%)) . .ri|
000002c0 67 68 74 28 70 6f 69 6e 74 65 72 25 28 6e 6f 64 |ght(pointer%(nod|
000002d0 65 25 2c 6c 65 66 74 25 29 29 0d 01 22 05 e1 0d |e%,left%)).."...|
000002e0 01 2c 13 dd 20 f2 72 69 67 68 74 28 6e 6f 64 65 |.,.. .right(node|
000002f0 25 29 0d 01 36 3c e7 20 70 6f 69 6e 74 65 72 25 |%)..6<. pointer%|
00000300 28 6e 6f 64 65 25 2c 72 69 67 68 74 25 29 3d 30 |(node%,right%)=0|
00000310 20 8c 20 70 6f 69 6e 74 65 72 25 28 6e 6f 64 65 | . pointer%(node|
00000320 25 2c 72 69 67 68 74 25 29 3d 49 25 3a e1 0d 01 |%,right%)=I%:...|
00000330 40 6f e7 20 77 6f 72 64 24 28 70 6f 69 6e 74 65 |@o. word$(pointe|
00000340 72 25 28 6e 6f 64 65 25 2c 72 69 67 68 74 25 29 |r%(node%,right%)|
00000350 29 3e 3d 77 6f 72 64 24 28 49 25 29 20 8c 20 f2 |)>=word$(I%) . .|
00000360 6c 65 66 74 28 70 6f 69 6e 74 65 72 25 28 6e 6f |left(pointer%(no|
00000370 64 65 25 2c 72 69 67 68 74 25 29 29 20 8b 20 f2 |de%,right%)) . .|
00000380 72 69 67 68 74 28 70 6f 69 6e 74 65 72 25 28 6e |right(pointer%(n|
00000390 6f 64 65 25 2c 72 69 67 68 74 25 29 29 0d 01 4a |ode%,right%))..J|
000003a0 05 e1 0d 01 54 22 dd 20 f2 70 72 69 6e 74 5f 73 |....T". .print_s|
000003b0 6f 72 74 65 64 28 49 25 29 3a e7 20 49 25 3d 30 |orted(I%):. I%=0|
000003c0 20 8c 20 e1 0d 01 5e 10 ea 20 40 25 3a 40 25 3d | . ...^.. @%:@%=|
000003d0 26 39 30 32 0d 01 68 25 f2 70 72 69 6e 74 5f 73 |&902..h%.print_s|
000003e0 6f 72 74 65 64 28 70 6f 69 6e 74 65 72 25 28 49 |orted(pointer%(I|
000003f0 25 2c 6c 65 66 74 25 29 29 0d 01 72 23 f1 20 89 |%,left%))..r#. .|
00000400 36 3b 77 6f 72 64 24 28 49 25 29 3b 8a 31 38 29 |6;word$(I%);.18)|
00000410 3b 22 20 28 22 2c 49 25 3b 22 29 22 0d 01 7c 26 |;" (",I%;")"..|&|
00000420 f2 70 72 69 6e 74 5f 73 6f 72 74 65 64 28 70 6f |.print_sorted(po|
00000430 69 6e 74 65 72 25 28 49 25 2c 72 69 67 68 74 25 |inter%(I%,right%|
00000440 29 29 0d 01 86 05 e1 0d 01 90 1d dd 20 f2 70 72 |)).......... .pr|
00000450 69 6e 74 5f 75 6e 73 6f 72 74 65 64 20 ea 20 40 |int_unsorted . @|
00000460 25 2c 49 25 0d 01 9a 0b 40 25 3d 26 39 30 35 0d |%,I%....@%=&905.|
00000470 01 a4 05 db 0d 01 ae 20 f1 27 89 37 3b 22 57 4f |....... .'.7;"WO|
00000480 52 44 22 3b 89 28 31 32 29 3b 22 50 4f 49 4e 54 |RD";.(12);"POINT|
00000490 45 52 53 22 0d 01 b8 16 f1 20 89 32 32 3b 22 6c |ERS"..... .22;"l|
000004a0 65 66 74 20 72 69 67 68 74 22 0d 01 c2 11 f1 20 |eft right"..... |
000004b0 89 33 3b c4 32 38 2c 22 2d 22 29 0d 01 cc 1d e3 |.3;.28,"-").....|
000004c0 20 49 25 3d 31 20 b8 20 6e 75 6d 62 65 72 5f 6f | I%=1 . number_o|
000004d0 66 5f 77 6f 72 64 73 25 0d 01 d6 38 f1 2c 49 25 |f_words%...8.,I%|
000004e0 2c 8a 36 29 77 6f 72 64 24 28 49 25 29 2c 8a 32 |,.6)word$(I%),.2|
000004f0 30 29 2c 70 6f 69 6e 74 65 72 25 28 49 25 2c 30 |0),pointer%(I%,0|
00000500 29 2c 70 6f 69 6e 74 65 72 25 28 49 25 2c 31 29 |),pointer%(I%,1)|
00000510 0d 01 e0 05 ed 0d 01 ea 05 e1 0d 01 f4 1b dd 20 |............... |
00000520 f2 72 61 6e 64 6f 6d 5f 77 6f 72 64 73 20 ea 20 |.random_words . |
00000530 49 25 2c 4a 25 0d 01 fe 31 f1 20 8a 32 30 2c 31 |I%,J%...1. .20,1|
00000540 30 29 3b 22 53 65 74 74 69 6e 67 20 75 70 20 61 |0);"Setting up a|
00000550 72 72 61 79 20 6f 66 20 72 61 6e 64 6f 6d 20 77 |rray of random w|
00000560 6f 72 64 73 2e 22 0d 02 08 1d e3 20 49 25 3d 31 |ords."..... I%=1|
00000570 20 b8 20 6e 75 6d 62 65 72 5f 6f 66 5f 77 6f 72 | . number_of_wor|
00000580 64 73 25 0d 02 12 1a 77 6f 72 64 24 28 49 25 29 |ds%....word$(I%)|
00000590 3d 22 31 32 33 34 35 36 37 38 39 30 22 0d 02 1c |="1234567890"...|
000005a0 10 77 6f 72 64 24 28 49 25 29 3d 22 22 0d 02 26 |.word$(I%)=""..&|
000005b0 13 e3 20 4a 25 3d 31 20 b8 20 b3 28 35 29 2b 35 |.. J%=1 . .(5)+5|
000005c0 0d 02 30 23 77 6f 72 64 24 28 49 25 29 3d 77 6f |..0#word$(I%)=wo|
000005d0 72 64 24 28 49 25 29 2b bd 28 36 34 2b b3 28 32 |rd$(I%)+.(64+.(2|
000005e0 36 29 29 0d 02 3a 05 ed 0d 02 44 14 70 6f 69 6e |6))..:....D.poin|
000005f0 74 65 72 25 28 49 25 2c 30 29 3d 30 0d 02 4e 14 |ter%(I%,0)=0..N.|
00000600 70 6f 69 6e 74 65 72 25 28 49 25 2c 31 29 3d 30 |pointer%(I%,1)=0|
00000610 0d 02 58 05 ed 0d 02 62 05 e1 0d 02 6c 05 ed 0d |..X....b....l...|
00000620 02 76 05 e1 0d ff |.v....|
00000626 
.