Home » CEEFAX disks » telesoftware16.adl » 18-06-89/QSText
18-06-89/QSText
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 » CEEFAX disks » telesoftware16.adl |
| Filename: | 18-06-89/QSText |
| Read OK: | ✔ |
| File size: | 0D4B bytes |
| Load address: | 0000 |
| Exec address: | FFFFFFFF |
File contents
Quicksort explained
--------- ---------
Author: Ian Rickards, January 1989
The Quicksort is a powerful and elegant sorting algorithm, using recursion
to good effect. There is an old computing joke that if you try to discover
the meaning of 'recursion' from a dictionary it will read 'see RECURSION'.
It is a method of breaking down a complicated problem into smaller, easier
sub-problems.
When you run the demonstration, the list is highlighted in pale blue to
show that it needs sorting. You can press any key to step through the
sequence.
Initially, the computer tries to rearrange the entire list into two
separate sub-lists: say A-M and N-Z. When you press a key, the computer
initialises two pointers - one at each end of the list. The reorganisation
is achieved by comparing the items at each pointer.
Step 1 - Swap the two items if they are out of sequence
If a swap occurs, then the pointers also exchange
Step 2 - Move the moveable pointer one place nearer to the super-pointer
This process repeats until the pointers meet. Notice that the item at the
super-pointer has been carried to its proper position, coloured yellow.
The preceding items are all above it, and the subsequent items are below -
so it must be in the right place.
When you press a key, the upper sub-list is highlighted and the quicksort
process begins all over again! This is RECURSION. In this way,
progressively smaller sub-lists need to be sorted. When a sub-list
contains less than two items, further sorting is not neccessary.
In case you wish to incorporate the quicksort into another program, I
conclude with a set of routines. Use *EXEC on this text file to load the
program into BASIC; if you RUN it, there is a simple demonstration.
9000 REM Quicksort routine
9010 REM Ian Rickards, January 1989
9020
9030 DEF PROCquicksort( lo%, hi% )
9040 LOCAL mid%
9050 mid% = FNheap
9060 IF mid% - 1 > lo% PROCquicksort( lo%, mid% - 1 )
9070 IF mid% + 1 < hi% PROCquicksort( mid% + 1, hi% )
9080 ENDPROC
9090
9100 DEF FNheap
9110 i% = lo%
9120 j% = hi%
9130 dir% = 1
9140 REPEAT
9150 IF in$( at%( i% ) ) > in$( at%( j% ) ) PROCswap
9160 IF dir% = 0 LET i% = i% + 1
9170 IF dir% = 1 LET j% = j% - 1
9180 UNTIL i% = j%
9190 = i%
9200
9210 DEF PROCswap
9220 dir% = dir% EOR 1
9230 remember% = at%( i% )
9240 at%( i% ) = at%( j% )
9250 at%( j% ) = remember%
9260 ENDPROC
As supplied, the routines quicksort a string array. To avoid the
time-consuming task of moving strings around in memory, an integer array is
used to map the sorted version onto the original. However, if you wish to
sort numeric data, use: 9150 IF at%( i% ) > at%( j% ) PROCswap
and store your data in at%( )
Finally, I include a short demonstration to illustrate the use of the
routines. Line 80 creates a direct map onto the unsorted data; it is
important that at%( ) is DIMensioned and initialized in this manner.
10 REM Simple example program
20
30 INPUT "How many strings to sort", no%
40 DIM in$( no% ), at%( no% )
50 FOR loop% = 1 TO no%
60 PRINT loop%;
70 INPUT ": " in$( loop% )
80 at%( loop% ) = loop%
90 NEXT
100
110 REM Call quicksort
120 PROCquicksort( 1, no% )
130
140 REM Display sorted list
150 PRINT "Quicksort completed"
160 FOR loop% = 1 TO no%
170 PRINT loop% ": " in$( at%( loop% ) )
180 NEXT
190 END
200
210
00000000 0d 51 75 69 63 6b 73 6f 72 74 20 65 78 70 6c 61 |.Quicksort expla| 00000010 69 6e 65 64 0d 2d 2d 2d 2d 2d 2d 2d 2d 2d 20 2d |ined.--------- -| 00000020 2d 2d 2d 2d 2d 2d 2d 2d 0d 0d 41 75 74 68 6f 72 |--------..Author| 00000030 3a 20 49 61 6e 20 52 69 63 6b 61 72 64 73 2c 20 |: Ian Rickards, | 00000040 4a 61 6e 75 61 72 79 20 31 39 38 39 0d 0d 0d 54 |January 1989...T| 00000050 68 65 20 51 75 69 63 6b 73 6f 72 74 20 69 73 20 |he Quicksort is | 00000060 61 20 70 6f 77 65 72 66 75 6c 20 61 6e 64 20 65 |a powerful and e| 00000070 6c 65 67 61 6e 74 20 73 6f 72 74 69 6e 67 20 61 |legant sorting a| 00000080 6c 67 6f 72 69 74 68 6d 2c 20 75 73 69 6e 67 20 |lgorithm, using | 00000090 72 65 63 75 72 73 69 6f 6e 0d 74 6f 20 67 6f 6f |recursion.to goo| 000000a0 64 20 65 66 66 65 63 74 2e 20 54 68 65 72 65 20 |d effect. There | 000000b0 69 73 20 61 6e 20 6f 6c 64 20 63 6f 6d 70 75 74 |is an old comput| 000000c0 69 6e 67 20 6a 6f 6b 65 20 74 68 61 74 20 69 66 |ing joke that if| 000000d0 20 79 6f 75 20 74 72 79 20 74 6f 20 64 69 73 63 | you try to disc| 000000e0 6f 76 65 72 0d 74 68 65 20 6d 65 61 6e 69 6e 67 |over.the meaning| 000000f0 20 6f 66 20 27 72 65 63 75 72 73 69 6f 6e 27 20 | of 'recursion' | 00000100 66 72 6f 6d 20 61 20 64 69 63 74 69 6f 6e 61 72 |from a dictionar| 00000110 79 20 69 74 20 77 69 6c 6c 20 72 65 61 64 20 27 |y it will read '| 00000120 73 65 65 20 52 45 43 55 52 53 49 4f 4e 27 2e 0d |see RECURSION'..| 00000130 49 74 20 69 73 20 61 20 6d 65 74 68 6f 64 20 6f |It is a method o| 00000140 66 20 62 72 65 61 6b 69 6e 67 20 64 6f 77 6e 20 |f breaking down | 00000150 61 20 63 6f 6d 70 6c 69 63 61 74 65 64 20 70 72 |a complicated pr| 00000160 6f 62 6c 65 6d 20 69 6e 74 6f 20 73 6d 61 6c 6c |oblem into small| 00000170 65 72 2c 20 65 61 73 69 65 72 0d 73 75 62 2d 70 |er, easier.sub-p| 00000180 72 6f 62 6c 65 6d 73 2e 0d 0d 57 68 65 6e 20 79 |roblems...When y| 00000190 6f 75 20 72 75 6e 20 74 68 65 20 64 65 6d 6f 6e |ou run the demon| 000001a0 73 74 72 61 74 69 6f 6e 2c 20 74 68 65 20 6c 69 |stration, the li| 000001b0 73 74 20 69 73 20 68 69 67 68 6c 69 67 68 74 65 |st is highlighte| 000001c0 64 20 69 6e 20 70 61 6c 65 20 62 6c 75 65 20 74 |d in pale blue t| 000001d0 6f 0d 73 68 6f 77 20 74 68 61 74 20 69 74 20 6e |o.show that it n| 000001e0 65 65 64 73 20 73 6f 72 74 69 6e 67 2e 20 59 6f |eeds sorting. Yo| 000001f0 75 20 63 61 6e 20 70 72 65 73 73 20 61 6e 79 20 |u can press any | 00000200 6b 65 79 20 74 6f 20 73 74 65 70 20 74 68 72 6f |key to step thro| 00000210 75 67 68 20 74 68 65 0d 73 65 71 75 65 6e 63 65 |ugh the.sequence| 00000220 2e 0d 0d 49 6e 69 74 69 61 6c 6c 79 2c 20 74 68 |...Initially, th| 00000230 65 20 63 6f 6d 70 75 74 65 72 20 74 72 69 65 73 |e computer tries| 00000240 20 74 6f 20 72 65 61 72 72 61 6e 67 65 20 74 68 | to rearrange th| 00000250 65 20 65 6e 74 69 72 65 20 6c 69 73 74 20 69 6e |e entire list in| 00000260 74 6f 20 74 77 6f 0d 73 65 70 61 72 61 74 65 20 |to two.separate | 00000270 73 75 62 2d 6c 69 73 74 73 3a 20 73 61 79 20 41 |sub-lists: say A| 00000280 2d 4d 20 61 6e 64 20 4e 2d 5a 2e 20 57 68 65 6e |-M and N-Z. When| 00000290 20 79 6f 75 20 70 72 65 73 73 20 61 20 6b 65 79 | you press a key| 000002a0 2c 20 74 68 65 20 63 6f 6d 70 75 74 65 72 0d 69 |, the computer.i| 000002b0 6e 69 74 69 61 6c 69 73 65 73 20 74 77 6f 20 70 |nitialises two p| 000002c0 6f 69 6e 74 65 72 73 20 2d 20 6f 6e 65 20 61 74 |ointers - one at| 000002d0 20 65 61 63 68 20 65 6e 64 20 6f 66 20 74 68 65 | each end of the| 000002e0 20 6c 69 73 74 2e 20 54 68 65 20 72 65 6f 72 67 | list. The reorg| 000002f0 61 6e 69 73 61 74 69 6f 6e 0d 69 73 20 61 63 68 |anisation.is ach| 00000300 69 65 76 65 64 20 62 79 20 63 6f 6d 70 61 72 69 |ieved by compari| 00000310 6e 67 20 74 68 65 20 69 74 65 6d 73 20 61 74 20 |ng the items at | 00000320 65 61 63 68 20 70 6f 69 6e 74 65 72 2e 0d 0d 53 |each pointer...S| 00000330 74 65 70 20 31 20 2d 20 53 77 61 70 20 74 68 65 |tep 1 - Swap the| 00000340 20 74 77 6f 20 69 74 65 6d 73 20 69 66 20 74 68 | two items if th| 00000350 65 79 20 61 72 65 20 6f 75 74 20 6f 66 20 73 65 |ey are out of se| 00000360 71 75 65 6e 63 65 0d 20 20 20 20 20 20 20 20 20 |quence. | 00000370 49 66 20 61 20 73 77 61 70 20 6f 63 63 75 72 73 |If a swap occurs| 00000380 2c 20 74 68 65 6e 20 74 68 65 20 70 6f 69 6e 74 |, then the point| 00000390 65 72 73 20 61 6c 73 6f 20 65 78 63 68 61 6e 67 |ers also exchang| 000003a0 65 0d 0d 53 74 65 70 20 32 20 2d 20 4d 6f 76 65 |e..Step 2 - Move| 000003b0 20 74 68 65 20 6d 6f 76 65 61 62 6c 65 20 70 6f | the moveable po| 000003c0 69 6e 74 65 72 20 6f 6e 65 20 70 6c 61 63 65 20 |inter one place | 000003d0 6e 65 61 72 65 72 20 74 6f 20 74 68 65 20 73 75 |nearer to the su| 000003e0 70 65 72 2d 70 6f 69 6e 74 65 72 0d 0d 54 68 69 |per-pointer..Thi| 000003f0 73 20 70 72 6f 63 65 73 73 20 72 65 70 65 61 74 |s process repeat| 00000400 73 20 75 6e 74 69 6c 20 74 68 65 20 70 6f 69 6e |s until the poin| 00000410 74 65 72 73 20 6d 65 65 74 2e 20 4e 6f 74 69 63 |ters meet. Notic| 00000420 65 20 74 68 61 74 20 74 68 65 20 69 74 65 6d 20 |e that the item | 00000430 61 74 20 74 68 65 0d 73 75 70 65 72 2d 70 6f 69 |at the.super-poi| 00000440 6e 74 65 72 20 68 61 73 20 62 65 65 6e 20 63 61 |nter has been ca| 00000450 72 72 69 65 64 20 74 6f 20 69 74 73 20 70 72 6f |rried to its pro| 00000460 70 65 72 20 70 6f 73 69 74 69 6f 6e 2c 20 63 6f |per position, co| 00000470 6c 6f 75 72 65 64 20 79 65 6c 6c 6f 77 2e 0d 54 |loured yellow..T| 00000480 68 65 20 70 72 65 63 65 64 69 6e 67 20 69 74 65 |he preceding ite| 00000490 6d 73 20 61 72 65 20 61 6c 6c 20 61 62 6f 76 65 |ms are all above| 000004a0 20 69 74 2c 20 61 6e 64 20 74 68 65 20 73 75 62 | it, and the sub| 000004b0 73 65 71 75 65 6e 74 20 69 74 65 6d 73 20 61 72 |sequent items ar| 000004c0 65 20 62 65 6c 6f 77 20 2d 0d 73 6f 20 69 74 20 |e below -.so it | 000004d0 6d 75 73 74 20 62 65 20 69 6e 20 74 68 65 20 72 |must be in the r| 000004e0 69 67 68 74 20 70 6c 61 63 65 2e 0d 0d 57 68 65 |ight place...Whe| 000004f0 6e 20 79 6f 75 20 70 72 65 73 73 20 61 20 6b 65 |n you press a ke| 00000500 79 2c 20 74 68 65 20 75 70 70 65 72 20 73 75 62 |y, the upper sub| 00000510 2d 6c 69 73 74 20 69 73 20 68 69 67 68 6c 69 67 |-list is highlig| 00000520 68 74 65 64 20 61 6e 64 20 74 68 65 20 71 75 69 |hted and the qui| 00000530 63 6b 73 6f 72 74 0d 70 72 6f 63 65 73 73 20 62 |cksort.process b| 00000540 65 67 69 6e 73 20 61 6c 6c 20 6f 76 65 72 20 61 |egins all over a| 00000550 67 61 69 6e 21 20 54 68 69 73 20 69 73 20 52 45 |gain! This is RE| 00000560 43 55 52 53 49 4f 4e 2e 20 49 6e 20 74 68 69 73 |CURSION. In this| 00000570 20 77 61 79 2c 0d 70 72 6f 67 72 65 73 73 69 76 | way,.progressiv| 00000580 65 6c 79 20 73 6d 61 6c 6c 65 72 20 73 75 62 2d |ely smaller sub-| 00000590 6c 69 73 74 73 20 6e 65 65 64 20 74 6f 20 62 65 |lists need to be| 000005a0 20 73 6f 72 74 65 64 2e 20 57 68 65 6e 20 61 20 | sorted. When a | 000005b0 73 75 62 2d 6c 69 73 74 0d 63 6f 6e 74 61 69 6e |sub-list.contain| 000005c0 73 20 6c 65 73 73 20 74 68 61 6e 20 74 77 6f 20 |s less than two | 000005d0 69 74 65 6d 73 2c 20 66 75 72 74 68 65 72 20 73 |items, further s| 000005e0 6f 72 74 69 6e 67 20 69 73 20 6e 6f 74 20 6e 65 |orting is not ne| 000005f0 63 63 65 73 73 61 72 79 2e 0d 0d 49 6e 20 63 61 |ccessary...In ca| 00000600 73 65 20 79 6f 75 20 77 69 73 68 20 74 6f 20 69 |se you wish to i| 00000610 6e 63 6f 72 70 6f 72 61 74 65 20 74 68 65 20 71 |ncorporate the q| 00000620 75 69 63 6b 73 6f 72 74 20 69 6e 74 6f 20 61 6e |uicksort into an| 00000630 6f 74 68 65 72 20 70 72 6f 67 72 61 6d 2c 20 49 |other program, I| 00000640 0d 63 6f 6e 63 6c 75 64 65 20 77 69 74 68 20 61 |.conclude with a| 00000650 20 73 65 74 20 6f 66 20 72 6f 75 74 69 6e 65 73 | set of routines| 00000660 2e 20 55 73 65 20 2a 45 58 45 43 20 6f 6e 20 74 |. Use *EXEC on t| 00000670 68 69 73 20 74 65 78 74 20 66 69 6c 65 20 74 6f |his text file to| 00000680 20 6c 6f 61 64 20 74 68 65 0d 70 72 6f 67 72 61 | load the.progra| 00000690 6d 20 69 6e 74 6f 20 42 41 53 49 43 3b 20 69 66 |m into BASIC; if| 000006a0 20 79 6f 75 20 52 55 4e 20 69 74 2c 20 74 68 65 | you RUN it, the| 000006b0 72 65 20 69 73 20 61 20 73 69 6d 70 6c 65 20 64 |re is a simple d| 000006c0 65 6d 6f 6e 73 74 72 61 74 69 6f 6e 2e 0d 0d 20 |emonstration... | 000006d0 39 30 30 30 20 52 45 4d 20 20 20 20 20 51 75 69 |9000 REM Qui| 000006e0 63 6b 73 6f 72 74 20 72 6f 75 74 69 6e 65 0d 20 |cksort routine. | 000006f0 39 30 31 30 20 52 45 4d 20 20 20 20 20 49 61 6e |9010 REM Ian| 00000700 20 52 69 63 6b 61 72 64 73 2c 20 4a 61 6e 75 61 | Rickards, Janua| 00000710 72 79 20 31 39 38 39 0d 20 39 30 32 30 20 0d 20 |ry 1989. 9020 . | 00000720 39 30 33 30 20 44 45 46 20 50 52 4f 43 71 75 69 |9030 DEF PROCqui| 00000730 63 6b 73 6f 72 74 28 20 6c 6f 25 2c 20 68 69 25 |cksort( lo%, hi%| 00000740 20 29 0d 20 39 30 34 30 20 4c 4f 43 41 4c 20 6d | ). 9040 LOCAL m| 00000750 69 64 25 0d 20 39 30 35 30 20 6d 69 64 25 20 3d |id%. 9050 mid% =| 00000760 20 46 4e 68 65 61 70 0d 20 39 30 36 30 20 49 46 | FNheap. 9060 IF| 00000770 20 6d 69 64 25 20 2d 20 31 20 3e 20 6c 6f 25 20 | mid% - 1 > lo% | 00000780 50 52 4f 43 71 75 69 63 6b 73 6f 72 74 28 20 6c |PROCquicksort( l| 00000790 6f 25 2c 20 6d 69 64 25 20 2d 20 31 20 29 0d 20 |o%, mid% - 1 ). | 000007a0 39 30 37 30 20 49 46 20 6d 69 64 25 20 2b 20 31 |9070 IF mid% + 1| 000007b0 20 3c 20 68 69 25 20 50 52 4f 43 71 75 69 63 6b | < hi% PROCquick| 000007c0 73 6f 72 74 28 20 6d 69 64 25 20 2b 20 31 2c 20 |sort( mid% + 1, | 000007d0 68 69 25 20 29 0d 20 39 30 38 30 20 45 4e 44 50 |hi% ). 9080 ENDP| 000007e0 52 4f 43 0d 20 39 30 39 30 20 0d 20 39 31 30 30 |ROC. 9090 . 9100| 000007f0 20 44 45 46 20 46 4e 68 65 61 70 0d 20 39 31 31 | DEF FNheap. 911| 00000800 30 20 69 25 20 3d 20 6c 6f 25 0d 20 39 31 32 30 |0 i% = lo%. 9120| 00000810 20 6a 25 20 3d 20 68 69 25 0d 20 39 31 33 30 20 | j% = hi%. 9130 | 00000820 64 69 72 25 20 3d 20 31 0d 20 39 31 34 30 20 52 |dir% = 1. 9140 R| 00000830 45 50 45 41 54 0d 20 39 31 35 30 20 49 46 20 69 |EPEAT. 9150 IF i| 00000840 6e 24 28 20 61 74 25 28 20 69 25 20 29 20 29 20 |n$( at%( i% ) ) | 00000850 3e 20 69 6e 24 28 20 61 74 25 28 20 6a 25 20 29 |> in$( at%( j% )| 00000860 20 29 20 50 52 4f 43 73 77 61 70 0d 20 39 31 36 | ) PROCswap. 916| 00000870 30 20 49 46 20 64 69 72 25 20 3d 20 30 20 4c 45 |0 IF dir% = 0 LE| 00000880 54 20 69 25 20 3d 20 69 25 20 2b 20 31 0d 20 39 |T i% = i% + 1. 9| 00000890 31 37 30 20 49 46 20 64 69 72 25 20 3d 20 31 20 |170 IF dir% = 1 | 000008a0 4c 45 54 20 6a 25 20 3d 20 6a 25 20 2d 20 31 0d |LET j% = j% - 1.| 000008b0 20 39 31 38 30 20 55 4e 54 49 4c 20 69 25 20 3d | 9180 UNTIL i% =| 000008c0 20 6a 25 0d 20 39 31 39 30 20 3d 20 69 25 0d 20 | j%. 9190 = i%. | 000008d0 39 32 30 30 20 0d 20 39 32 31 30 20 44 45 46 20 |9200 . 9210 DEF | 000008e0 50 52 4f 43 73 77 61 70 0d 20 39 32 32 30 20 64 |PROCswap. 9220 d| 000008f0 69 72 25 20 3d 20 64 69 72 25 20 45 4f 52 20 31 |ir% = dir% EOR 1| 00000900 0d 20 39 32 33 30 20 72 65 6d 65 6d 62 65 72 25 |. 9230 remember%| 00000910 20 3d 20 61 74 25 28 20 69 25 20 29 0d 20 39 32 | = at%( i% ). 92| 00000920 34 30 20 61 74 25 28 20 69 25 20 29 20 3d 20 61 |40 at%( i% ) = a| 00000930 74 25 28 20 6a 25 20 29 0d 20 39 32 35 30 20 61 |t%( j% ). 9250 a| 00000940 74 25 28 20 6a 25 20 29 20 3d 20 72 65 6d 65 6d |t%( j% ) = remem| 00000950 62 65 72 25 0d 20 39 32 36 30 20 45 4e 44 50 52 |ber%. 9260 ENDPR| 00000960 4f 43 0d 0d 41 73 20 73 75 70 70 6c 69 65 64 2c |OC..As supplied,| 00000970 20 74 68 65 20 72 6f 75 74 69 6e 65 73 20 71 75 | the routines qu| 00000980 69 63 6b 73 6f 72 74 20 61 20 73 74 72 69 6e 67 |icksort a string| 00000990 20 61 72 72 61 79 2e 20 54 6f 20 61 76 6f 69 64 | array. To avoid| 000009a0 20 74 68 65 0d 74 69 6d 65 2d 63 6f 6e 73 75 6d | the.time-consum| 000009b0 69 6e 67 20 74 61 73 6b 20 6f 66 20 6d 6f 76 69 |ing task of movi| 000009c0 6e 67 20 73 74 72 69 6e 67 73 20 61 72 6f 75 6e |ng strings aroun| 000009d0 64 20 69 6e 20 6d 65 6d 6f 72 79 2c 20 61 6e 20 |d in memory, an | 000009e0 69 6e 74 65 67 65 72 20 61 72 72 61 79 20 69 73 |integer array is| 000009f0 0d 75 73 65 64 20 74 6f 20 6d 61 70 20 74 68 65 |.used to map the| 00000a00 20 73 6f 72 74 65 64 20 76 65 72 73 69 6f 6e 20 | sorted version | 00000a10 6f 6e 74 6f 20 74 68 65 20 6f 72 69 67 69 6e 61 |onto the origina| 00000a20 6c 2e 20 48 6f 77 65 76 65 72 2c 20 69 66 20 79 |l. However, if y| 00000a30 6f 75 20 77 69 73 68 20 74 6f 0d 73 6f 72 74 20 |ou wish to.sort | 00000a40 6e 75 6d 65 72 69 63 20 64 61 74 61 2c 20 75 73 |numeric data, us| 00000a50 65 3a 20 39 31 35 30 20 49 46 20 61 74 25 28 20 |e: 9150 IF at%( | 00000a60 69 25 20 29 20 3e 20 61 74 25 28 20 6a 25 20 29 |i% ) > at%( j% )| 00000a70 20 50 52 4f 43 73 77 61 70 0d 61 6e 64 20 73 74 | PROCswap.and st| 00000a80 6f 72 65 20 79 6f 75 72 20 64 61 74 61 20 69 6e |ore your data in| 00000a90 20 61 74 25 28 20 29 0d 0d 46 69 6e 61 6c 6c 79 | at%( )..Finally| 00000aa0 2c 20 49 20 69 6e 63 6c 75 64 65 20 61 20 73 68 |, I include a sh| 00000ab0 6f 72 74 20 64 65 6d 6f 6e 73 74 72 61 74 69 6f |ort demonstratio| 00000ac0 6e 20 74 6f 20 69 6c 6c 75 73 74 72 61 74 65 20 |n to illustrate | 00000ad0 74 68 65 20 75 73 65 20 6f 66 20 74 68 65 0d 72 |the use of the.r| 00000ae0 6f 75 74 69 6e 65 73 2e 20 4c 69 6e 65 20 38 30 |outines. Line 80| 00000af0 20 63 72 65 61 74 65 73 20 61 20 64 69 72 65 63 | creates a direc| 00000b00 74 20 6d 61 70 20 6f 6e 74 6f 20 74 68 65 20 75 |t map onto the u| 00000b10 6e 73 6f 72 74 65 64 20 64 61 74 61 3b 20 69 74 |nsorted data; it| 00000b20 20 69 73 0d 69 6d 70 6f 72 74 61 6e 74 20 74 68 | is.important th| 00000b30 61 74 20 61 74 25 28 20 29 20 69 73 20 44 49 4d |at at%( ) is DIM| 00000b40 65 6e 73 69 6f 6e 65 64 20 61 6e 64 20 69 6e 69 |ensioned and ini| 00000b50 74 69 61 6c 69 7a 65 64 20 69 6e 20 74 68 69 73 |tialized in this| 00000b60 20 6d 61 6e 6e 65 72 2e 0d 0d 20 20 20 31 30 20 | manner... 10 | 00000b70 52 45 4d 20 20 20 20 20 53 69 6d 70 6c 65 20 65 |REM Simple e| 00000b80 78 61 6d 70 6c 65 20 70 72 6f 67 72 61 6d 0d 20 |xample program. | 00000b90 20 20 32 30 20 0d 20 20 20 33 30 20 49 4e 50 55 | 20 . 30 INPU| 00000ba0 54 20 22 48 6f 77 20 6d 61 6e 79 20 73 74 72 69 |T "How many stri| 00000bb0 6e 67 73 20 74 6f 20 73 6f 72 74 22 2c 20 6e 6f |ngs to sort", no| 00000bc0 25 0d 20 20 20 34 30 20 44 49 4d 20 69 6e 24 28 |%. 40 DIM in$(| 00000bd0 20 6e 6f 25 20 29 2c 20 61 74 25 28 20 6e 6f 25 | no% ), at%( no%| 00000be0 20 29 0d 20 20 20 35 30 20 46 4f 52 20 6c 6f 6f | ). 50 FOR loo| 00000bf0 70 25 20 3d 20 31 20 54 4f 20 6e 6f 25 0d 20 20 |p% = 1 TO no%. | 00000c00 20 36 30 20 50 52 49 4e 54 20 6c 6f 6f 70 25 3b | 60 PRINT loop%;| 00000c10 0d 20 20 20 37 30 20 49 4e 50 55 54 20 22 3a 20 |. 70 INPUT ": | 00000c20 22 20 69 6e 24 28 20 6c 6f 6f 70 25 20 29 0d 20 |" in$( loop% ). | 00000c30 20 20 38 30 20 61 74 25 28 20 6c 6f 6f 70 25 20 | 80 at%( loop% | 00000c40 29 20 3d 20 6c 6f 6f 70 25 0d 20 20 20 39 30 20 |) = loop%. 90 | 00000c50 4e 45 58 54 0d 20 20 31 30 30 20 0d 20 20 31 31 |NEXT. 100 . 11| 00000c60 30 20 52 45 4d 20 20 20 20 20 43 61 6c 6c 20 71 |0 REM Call q| 00000c70 75 69 63 6b 73 6f 72 74 0d 20 20 31 32 30 20 50 |uicksort. 120 P| 00000c80 52 4f 43 71 75 69 63 6b 73 6f 72 74 28 20 31 2c |ROCquicksort( 1,| 00000c90 20 6e 6f 25 20 29 0d 20 20 31 33 30 20 0d 20 20 | no% ). 130 . | 00000ca0 31 34 30 20 52 45 4d 20 20 20 20 20 44 69 73 70 |140 REM Disp| 00000cb0 6c 61 79 20 73 6f 72 74 65 64 20 6c 69 73 74 0d |lay sorted list.| 00000cc0 20 20 31 35 30 20 50 52 49 4e 54 20 22 51 75 69 | 150 PRINT "Qui| 00000cd0 63 6b 73 6f 72 74 20 63 6f 6d 70 6c 65 74 65 64 |cksort completed| 00000ce0 22 0d 20 20 31 36 30 20 46 4f 52 20 6c 6f 6f 70 |". 160 FOR loop| 00000cf0 25 20 3d 20 31 20 54 4f 20 6e 6f 25 0d 20 20 31 |% = 1 TO no%. 1| 00000d00 37 30 20 50 52 49 4e 54 20 6c 6f 6f 70 25 20 22 |70 PRINT loop% "| 00000d10 3a 20 22 20 69 6e 24 28 20 61 74 25 28 20 6c 6f |: " in$( at%( lo| 00000d20 6f 70 25 20 29 20 29 0d 20 20 31 38 30 20 4e 45 |op% ) ). 180 NE| 00000d30 58 54 0d 20 20 31 39 30 20 45 4e 44 0d 20 20 32 |XT. 190 END. 2| 00000d40 30 30 20 0d 20 20 32 31 30 20 0d |00 . 210 .| 00000d4b
18-06-89/QSText.m0
18-06-89/QSText.m1
18-06-89/QSText.m2
18-06-89/QSText.m4
18-06-89/QSText.m5
.