[address omitted]
May 21, 1990
Dear George,
It seems to me like last time, you asked me something about sorting a database. Something about several people were trying to write a database to take advantage of the RAMDISK, with records of about 64 or 256 bytes.
In answer to the first implied question, for something of that type, if you are actually talking about moving things when you sort them – as opposed to moving pointers – the fastest sort is something called a binary insertion sort. Well, even if you aren’t talking about moving things.
Let me back up. There are 3 basic types of sort routines. There is the ever-popular bubble sort, there is the swap sort (which really isn’t much different), and there is the insertion sort. There are actually several types of insertion sort as well, one of which is the binary insertion sort.
The reason that a binary insertion sort is better on average than the others is that it requires fewer comparisons on average. That is, given a randomly ordered list of, say 100 items, a typical bubble sort, swap sort, or a standard insertion sort will have to perform 50*99/2=2475 comparisons, while a binary insertion sort only performs 580 comparisons.
There is a down side, though. The 2475 is an average figure – it could actually be anywhere from 99 to 4950, where as the binary insertion sort will always perform 580 comparisons. Which means that if the list was almost ordered, it is actually slower, but not by too much. It also involves a little more overhead in determining which numbers it has to check. Which means it may actually take longer for each comparison. But it really does make up for it in the number of comparisons.
Let me pull out a rather extreme example. Suppose you create a Tasword file which is filled with random numbers. I did just this earlier, simply by typing FOR i=33280 TO 49151: POKE i,INT (10*RND)+48:NEXT i. This will take about 10 minutes to create a file of 248 lines of random numbers. Now, take your program for sorting Tasword files, and see how long it takes to sort that one. I just finished writing a binary insertion sort for Tasword, and it took me 6.57 seconds to sort this file (I had the computer time it, by entering PRINT #4: POKE 23672,0: RANDOMIZE USR sort: PRINT (PEEK 23672+256*PEEK 23673)/60.
Anyway, that answers part of your question. The obvious second question, though, is how to sort something which might occupy a couple of different banks of the RAMDISK. This could be a bit of a problem, since it can’t all be kept in main memory at once to sort it. That means it will have to be sorted a bit at a time.
Let’s consider an extreme case. Suppose someone has taken up all 8 banks of his RAMDISK. If he wanted to re-sort it, he would have to sort each one seperately, and then divide each bank into 8 pieces (since he had 8 banks), and put all the lowest pieces in 1 bank, etc., and sort each bank again.
On second thought, let’s forget that. It is way too much hassle. If you are considering files that are too big for main memory, you better forget actually moving everything around. Use an indexed approach – it will be faster and less work anyway. Even if each record is only 64 bytes, this means there will be at most 4096 records in the entire RAMDISK. Each pointer would then need to be 2 bytes, so your index would be 8192 bytes long. You probably also need a list of unused records, just like the list on a disk. You might even consider this like a disk in that sense, just a disk whose blocks are a lot smaller than you are used to.
In some sense, it might be better to have records of 128 bytes or bigger. Then you will have 256 or less records in any given bank, so the pointer could consist of 1 byte for the bank, and 1 for which record in the bank.
Regardless, you will find it much easier to sort an index than to sort the file itself. Instead of having to move all the records, possibly even having to swap them between banks, you only have to move the index.
Just for reference, consider the Tasword file we used earlier. Of that 6.57 seconds it took to sort it, I know that only .3 was actually required for the comparisons and overhead. The other 6.27 seconds was involved in actually moving text. If I could have used an index in that example, the moving pointers would have taken less time than the comparisons. In other words, using an index would probably have accomplished the same effect in under 1 second! In practical terms, it is the difference between sorting your hypothetical database in half a minute and in half an hour.
I am afraid that the same isn’t true in BASIC – I have the equivalent programs in BASIC, and there is no real gain in using indexes then. Still, here is what the equivalent program would look like in BASIC:
1 REM Indexed Binary sort
2 REM Variables:
3 REM a$(n)=array to sort
4 REM i(n) = index
5 REM n = number of records
6 REM hi = top of search
7 REM lo = bottom of search
8 REM pt = middle of search
10 LET i(1)=1
11 FOR i=2 TO n
12 LET t$=a$(i)
13 LET hi=i
14 LET lo=0
15 LET pt=int ((hi+lo)/2)
16 IF pt=lo THEN GO TO 25
17 IF a$(i(pt))>t$ THEN GO TO 20
18 LET lo=pt
19 GO TO 15
20 LET hi=pt
21 GO TO 15
25 FOR j=i TO hi+1 STEP -1
26 LET i(j)=i(j-1)
27 NEXT j
28 LET i(hi)=i
29 NEXT i
Sort for Tasword only, using binary insertion routine
2 CLEAR 32998
3 LET sort=33000
10 LET a=10: LET b=11: LET c=12: LET d=13: LET e=14: LET f=15
11 LET x=sort-1
12 READ a$: IF a$="END" THEN GO TO 15
13 FOR i=1 TO LEN a$ STEP 3: POKE x,16*VAL a$(i)+VAL a$(i+1): LET x=x+1: NEXT i
14 GO TO 12
15 PRINT "To use, LOAD file, then:"
16 PRINT '"RANDOMIZE USR ";sort
20 PRINT AT 5,0;"Sort on a different column","(1 <= col <= 64) by:"
21 PRINT '"POKE ";sort-1;",(col)"
999 STOP
1000 DATA "01": REM Default column
1001 DATA "21 00 CD 3E 20 2B BE 28"
1002 DATA "FC 01 40 00 09 7D E6 C0"
1003 DATA "6F E5 21 00 82 01 40 00"
1004 DATA "09 D1 ED 52 D0 19 D5 11"
1005 DATA "C0 81 ED 53 7A 81 E5 E5"
1006 DATA "ED B0 E1 22 7C 81 2A 7C"
1007 DATA "81 ED 5B 7A 81 A7 ED 52"
1008 DATA "CB 1C CB 1D 7D E6 C0 6F"
1009 DATA "B4 28 0D 19 E5 CD 5E 81"
1010 DATA "E1 38 E0 22 7A 81 18 DE"
1011 DATA "E1 ED 5B 7C 81 A7 E5 2B"
1012 DATA "ED 52 38 16 44 4D 19 03"
1013 DATA "11 40 00 EB 19 EB ED B8"
1014 DATA "23 11 C0 81 01 40 00 EB"
1015 DATA "ED B0 E1 18 A0 00"
1019 REM Compare subroutine
1020 DATA "3A E7 80 3D 47 3E 40 11"
1021 DATA "C0 81 28 06 90 C8 23 13"
1022 DATA "10 FC 47 1A BE C0 23 13"
1023 DATA "10 F9 C9 00"
1030 DATA "END"
9800 RANDOMIZE USR 100: SAVE "Tasort.CI"CODE 32999,146
9810 STOP
9900 RANDOMIZE USR 100: SAVE "Tasort.BI" LINE 1
2 CLEAR 32998
3 LET sort=33000
5 READ col: POKE sort-1,col
10 LET a=10: LET b=11: LET c=12: LET d=13: LET e=14: LET f=15
11 LET x=sort
12 READ a$: IF a$="END" THEN GO TO 15
Media
Note: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.