Home » Archimedes archive » Acorn User » AU 1998-03 A.adf » Features » DiffDim2/Program2
DiffDim2/Program2
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 » Acorn User » AU 1998-03 A.adf » Features |
| Filename: | DiffDim2/Program2 |
| Read OK: | ✔ |
| File size: | 05CE bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
File contents
10REM Program 2 20REM 30REM Demonstrate the operation of radix sort 40: 50max%=100000 60REM Arrays to hold digits, sorted digits and count values 70DIM array%(max%),altarray%(max%),countarray%(31) 80: 90num%=10 100REPEAT 110: 120: 130REM Generate list of random numbers in range 1-32767, ie three 5 bit radix 140FORn%=0 TO num% 150array%(n%)=RND(32767) 160NEXT 170: 180REM Sort the values 190PRINT "Sorting ";num%;" random values (in BASIC)" 200TIME=0 210REM Loop through all radix 220FOR radix%=0 TO 2 230 PROCcount_sort(radix%) 240NEXT 250T=TIME 260PRINT "Time taken = ";T/100;" = ";T/(100*num%);" per element" 270num%=num%*10 280UNTIL num%>max% 290: 300A%=GET 310: 320REM Print the sorted values 330FORn%=0 TO num% 340 PRINT array%(n%) 350NEXT 360END 370: 380DEFPROCcount_sort(radix%) 390PRINT"Sorting on radix: ";radix% 400: 410REM Zero counting array 420countarray%()=0 430: 440REM Calculate mask to extract digit value 450shf%=radix%*5:msk%=31<<shf% 460: 470REM Run through array counting number of each digit value present 480FORn%=0 TO num% 490countarray%((array%(n%) AND msk%)>>shf%)+=1 500NEXT 510: 520REM Calculate the position each digit value will occupy in the output array 530countarray%(1)-=1 540FORn%=1 TO 31 550countarray%(n%)+=countarray%(n%-1) 560NEXT 570: 580REM Place each value in the correct location and decrement that location 590FORn%=num% TO 0 STEP -1 600i%=(array%(n%) AND msk%)>>shf% 610altarray%(countarray%(i%))=array%(n%) 620countarray%(i%)-=1 630NEXT 640: 650REM Copy alternate array into primary array 660FORn%=0 TO num% 670array%(n%)=altarray%(n%) 680NEXT 690ENDPROC
� Program 2 � -� Demonstrate the operation of radix sort (: 2max%=100000 <;� Arrays to hold digits, sorted digits and count values F2� array%(max%),altarray%(max%),countarray%(31) P: Z num%=10 d� n: x: �L� Generate list of random numbers in range 1-32767, ie three 5 bit radix ��n%=0 � num% �array%(n%)=�(32767) �� �: �� Sort the values �1� "Sorting ";num%;" random values (in BASIC)" ��=0 � � Loop through all radix �� radix%=0 � 2 � �count_sort(radix%) �� �T=� =� "Time taken = ";T/100;" = ";T/(100*num%);" per element" num%=num%*10 � num%>max% ": ,A%=� 6: @ � Print the sorted values J�n%=0 � num% T � array%(n%) ^� h� r: |��count_sort(radix%) � �"Sorting on radix: ";radix% �: �� Zero counting array �countarray%()=0 �: �+� Calculate mask to extract digit value � shf%=radix%*5:msk%=31<<shf% �: �C� Run through array counting number of each digit value present ��n%=0 � num% �-countarray%((array%(n%) � msk%)>>shf%)+=1 �� �: M� Calculate the position each digit value will occupy in the output array countarray%(1)-=1 �n%=1 � 31 &&countarray%(n%)+=countarray%(n%-1) 0� :: DJ� Place each value in the correct location and decrement that location N�n%=num% � 0 � -1 X i%=(array%(n%) � msk%)>>shf% b)altarray%(countarray%(i%))=array%(n%) lcountarray%(i%)-=1 v� �: �-� Copy alternate array into primary array ��n%=0 � num% � array%(n%)=altarray%(n%) �� �� �
00000000 0d 00 0a 0f f4 20 50 72 6f 67 72 61 6d 20 32 0d |..... Program 2.| 00000010 00 14 05 f4 0d 00 1e 2d f4 20 44 65 6d 6f 6e 73 |.......-. Demons| 00000020 74 72 61 74 65 20 74 68 65 20 6f 70 65 72 61 74 |trate the operat| 00000030 69 6f 6e 20 6f 66 20 72 61 64 69 78 20 73 6f 72 |ion of radix sor| 00000040 74 0d 00 28 05 3a 0d 00 32 0f 6d 61 78 25 3d 31 |t..(.:..2.max%=1| 00000050 30 30 30 30 30 0d 00 3c 3b f4 20 41 72 72 61 79 |00000..<;. Array| 00000060 73 20 74 6f 20 68 6f 6c 64 20 64 69 67 69 74 73 |s to hold digits| 00000070 2c 20 73 6f 72 74 65 64 20 64 69 67 69 74 73 20 |, sorted digits | 00000080 61 6e 64 20 63 6f 75 6e 74 20 76 61 6c 75 65 73 |and count values| 00000090 0d 00 46 32 de 20 61 72 72 61 79 25 28 6d 61 78 |..F2. array%(max| 000000a0 25 29 2c 61 6c 74 61 72 72 61 79 25 28 6d 61 78 |%),altarray%(max| 000000b0 25 29 2c 63 6f 75 6e 74 61 72 72 61 79 25 28 33 |%),countarray%(3| 000000c0 31 29 0d 00 50 05 3a 0d 00 5a 0b 6e 75 6d 25 3d |1)..P.:..Z.num%=| 000000d0 31 30 0d 00 64 05 f5 0d 00 6e 05 3a 0d 00 78 05 |10..d....n.:..x.| 000000e0 3a 0d 00 82 4c f4 20 47 65 6e 65 72 61 74 65 20 |:...L. Generate | 000000f0 6c 69 73 74 20 6f 66 20 72 61 6e 64 6f 6d 20 6e |list of random n| 00000100 75 6d 62 65 72 73 20 69 6e 20 72 61 6e 67 65 20 |umbers in range | 00000110 31 2d 33 32 37 36 37 2c 20 69 65 20 74 68 72 65 |1-32767, ie thre| 00000120 65 20 35 20 62 69 74 20 72 61 64 69 78 0d 00 8c |e 5 bit radix...| 00000130 10 e3 6e 25 3d 30 20 b8 20 6e 75 6d 25 0d 00 96 |..n%=0 . num%...| 00000140 17 61 72 72 61 79 25 28 6e 25 29 3d b3 28 33 32 |.array%(n%)=.(32| 00000150 37 36 37 29 0d 00 a0 05 ed 0d 00 aa 05 3a 0d 00 |767).........:..| 00000160 b4 15 f4 20 53 6f 72 74 20 74 68 65 20 76 61 6c |... Sort the val| 00000170 75 65 73 0d 00 be 31 f1 20 22 53 6f 72 74 69 6e |ues...1. "Sortin| 00000180 67 20 22 3b 6e 75 6d 25 3b 22 20 72 61 6e 64 6f |g ";num%;" rando| 00000190 6d 20 76 61 6c 75 65 73 20 28 69 6e 20 42 41 53 |m values (in BAS| 000001a0 49 43 29 22 0d 00 c8 07 d1 3d 30 0d 00 d2 1c f4 |IC)".....=0.....| 000001b0 20 4c 6f 6f 70 20 74 68 72 6f 75 67 68 20 61 6c | Loop through al| 000001c0 6c 20 72 61 64 69 78 0d 00 dc 12 e3 20 72 61 64 |l radix..... rad| 000001d0 69 78 25 3d 30 20 b8 20 32 0d 00 e6 19 20 20 f2 |ix%=0 . 2.... .| 000001e0 63 6f 75 6e 74 5f 73 6f 72 74 28 72 61 64 69 78 |count_sort(radix| 000001f0 25 29 0d 00 f0 05 ed 0d 00 fa 07 54 3d 91 0d 01 |%).........T=...| 00000200 04 3d f1 20 22 54 69 6d 65 20 74 61 6b 65 6e 20 |.=. "Time taken | 00000210 3d 20 22 3b 54 2f 31 30 30 3b 22 20 3d 20 22 3b |= ";T/100;" = ";| 00000220 54 2f 28 31 30 30 2a 6e 75 6d 25 29 3b 22 20 70 |T/(100*num%);" p| 00000230 65 72 20 65 6c 65 6d 65 6e 74 22 0d 01 0e 10 6e |er element"....n| 00000240 75 6d 25 3d 6e 75 6d 25 2a 31 30 0d 01 18 0f fd |um%=num%*10.....| 00000250 20 6e 75 6d 25 3e 6d 61 78 25 0d 01 22 05 3a 0d | num%>max%..".:.| 00000260 01 2c 08 41 25 3d a5 0d 01 36 05 3a 0d 01 40 1d |.,.A%=...6.:..@.| 00000270 f4 20 50 72 69 6e 74 20 74 68 65 20 73 6f 72 74 |. Print the sort| 00000280 65 64 20 76 61 6c 75 65 73 0d 01 4a 10 e3 6e 25 |ed values..J..n%| 00000290 3d 30 20 b8 20 6e 75 6d 25 0d 01 54 12 20 20 f1 |=0 . num%..T. .| 000002a0 20 61 72 72 61 79 25 28 6e 25 29 0d 01 5e 05 ed | array%(n%)..^..| 000002b0 0d 01 68 05 e0 0d 01 72 05 3a 0d 01 7c 18 dd f2 |..h....r.:..|...| 000002c0 63 6f 75 6e 74 5f 73 6f 72 74 28 72 61 64 69 78 |count_sort(radix| 000002d0 25 29 0d 01 86 20 f1 22 53 6f 72 74 69 6e 67 20 |%)... ."Sorting | 000002e0 6f 6e 20 72 61 64 69 78 3a 20 22 3b 72 61 64 69 |on radix: ";radi| 000002f0 78 25 0d 01 90 05 3a 0d 01 9a 19 f4 20 5a 65 72 |x%....:..... Zer| 00000300 6f 20 63 6f 75 6e 74 69 6e 67 20 61 72 72 61 79 |o counting array| 00000310 0d 01 a4 13 63 6f 75 6e 74 61 72 72 61 79 25 28 |....countarray%(| 00000320 29 3d 30 0d 01 ae 05 3a 0d 01 b8 2b f4 20 43 61 |)=0....:...+. Ca| 00000330 6c 63 75 6c 61 74 65 20 6d 61 73 6b 20 74 6f 20 |lculate mask to | 00000340 65 78 74 72 61 63 74 20 64 69 67 69 74 20 76 61 |extract digit va| 00000350 6c 75 65 0d 01 c2 1f 73 68 66 25 3d 72 61 64 69 |lue....shf%=radi| 00000360 78 25 2a 35 3a 6d 73 6b 25 3d 33 31 3c 3c 73 68 |x%*5:msk%=31<<sh| 00000370 66 25 0d 01 cc 05 3a 0d 01 d6 43 f4 20 52 75 6e |f%....:...C. Run| 00000380 20 74 68 72 6f 75 67 68 20 61 72 72 61 79 20 63 | through array c| 00000390 6f 75 6e 74 69 6e 67 20 6e 75 6d 62 65 72 20 6f |ounting number o| 000003a0 66 20 65 61 63 68 20 64 69 67 69 74 20 76 61 6c |f each digit val| 000003b0 75 65 20 70 72 65 73 65 6e 74 0d 01 e0 10 e3 6e |ue present.....n| 000003c0 25 3d 30 20 b8 20 6e 75 6d 25 0d 01 ea 2d 63 6f |%=0 . num%...-co| 000003d0 75 6e 74 61 72 72 61 79 25 28 28 61 72 72 61 79 |untarray%((array| 000003e0 25 28 6e 25 29 20 80 20 6d 73 6b 25 29 3e 3e 73 |%(n%) . msk%)>>s| 000003f0 68 66 25 29 2b 3d 31 0d 01 f4 05 ed 0d 01 fe 05 |hf%)+=1.........| 00000400 3a 0d 02 08 4d f4 20 43 61 6c 63 75 6c 61 74 65 |:...M. Calculate| 00000410 20 74 68 65 20 70 6f 73 69 74 69 6f 6e 20 65 61 | the position ea| 00000420 63 68 20 64 69 67 69 74 20 76 61 6c 75 65 20 77 |ch digit value w| 00000430 69 6c 6c 20 6f 63 63 75 70 79 20 69 6e 20 74 68 |ill occupy in th| 00000440 65 20 6f 75 74 70 75 74 20 61 72 72 61 79 0d 02 |e output array..| 00000450 12 15 63 6f 75 6e 74 61 72 72 61 79 25 28 31 29 |..countarray%(1)| 00000460 2d 3d 31 0d 02 1c 0e e3 6e 25 3d 31 20 b8 20 33 |-=1.....n%=1 . 3| 00000470 31 0d 02 26 26 63 6f 75 6e 74 61 72 72 61 79 25 |1..&&countarray%| 00000480 28 6e 25 29 2b 3d 63 6f 75 6e 74 61 72 72 61 79 |(n%)+=countarray| 00000490 25 28 6e 25 2d 31 29 0d 02 30 05 ed 0d 02 3a 05 |%(n%-1)..0....:.| 000004a0 3a 0d 02 44 4a f4 20 50 6c 61 63 65 20 65 61 63 |:..DJ. Place eac| 000004b0 68 20 76 61 6c 75 65 20 69 6e 20 74 68 65 20 63 |h value in the c| 000004c0 6f 72 72 65 63 74 20 6c 6f 63 61 74 69 6f 6e 20 |orrect location | 000004d0 61 6e 64 20 64 65 63 72 65 6d 65 6e 74 20 74 68 |and decrement th| 000004e0 61 74 20 6c 6f 63 61 74 69 6f 6e 0d 02 4e 15 e3 |at location..N..| 000004f0 6e 25 3d 6e 75 6d 25 20 b8 20 30 20 88 20 2d 31 |n%=num% . 0 . -1| 00000500 0d 02 58 20 69 25 3d 28 61 72 72 61 79 25 28 6e |..X i%=(array%(n| 00000510 25 29 20 80 20 6d 73 6b 25 29 3e 3e 73 68 66 25 |%) . msk%)>>shf%| 00000520 0d 02 62 29 61 6c 74 61 72 72 61 79 25 28 63 6f |..b)altarray%(co| 00000530 75 6e 74 61 72 72 61 79 25 28 69 25 29 29 3d 61 |untarray%(i%))=a| 00000540 72 72 61 79 25 28 6e 25 29 0d 02 6c 16 63 6f 75 |rray%(n%)..l.cou| 00000550 6e 74 61 72 72 61 79 25 28 69 25 29 2d 3d 31 0d |ntarray%(i%)-=1.| 00000560 02 76 05 ed 0d 02 80 05 3a 0d 02 8a 2d f4 20 43 |.v......:...-. C| 00000570 6f 70 79 20 61 6c 74 65 72 6e 61 74 65 20 61 72 |opy alternate ar| 00000580 72 61 79 20 69 6e 74 6f 20 70 72 69 6d 61 72 79 |ray into primary| 00000590 20 61 72 72 61 79 0d 02 94 10 e3 6e 25 3d 30 20 | array.....n%=0 | 000005a0 b8 20 6e 75 6d 25 0d 02 9e 1c 61 72 72 61 79 25 |. num%....array%| 000005b0 28 6e 25 29 3d 61 6c 74 61 72 72 61 79 25 28 6e |(n%)=altarray%(n| 000005c0 25 29 0d 02 a8 05 ed 0d 02 b2 05 e1 0d ff |%)............| 000005ce
.