0 IFA=0THENA=1:LOAD"[209][215][201][208][197]",8,1
5 REM@ S 1024
10 POKE45,124:POKE46,103:CLR:MX=200:DIMAR(200),SL(10),SR(10),TE$(500),S(11),F(8)
11 DV=PEEK(186):IFDV<8THENDV=8
12 LOAD"[209][215][201][208][197]",DV,128
20 DEFFNHZ(X)=INT(X/16)
30 DEFFNPS(X)=4^(3-(XAND12)/4)
40 DEFFNCL(X)=(XAND3)
50 DEFFNME(Z)=57344+INT((Y-1)/8)*320+X*8+((Y-1)AND7)
60 POKE53280,0:POKE53281,0:POKE53270,200
70 POKE56576,4:POKE53272,18:POKE648,196:POKE53265,27
80 FORX=1TO9:READMN$(X):NEXT
90 DATA"1.[160][201]NSERTION[160][211]ORT[160][160][160][160][160][160][160][160]","2.[160][211]ELECTION[160][211]ORT[160][160][160][160][160][160][160][160]"
100 DATA"3.[160][196]ELAYED[160][211]ELECTION[160][211]ORT","4.[160][194]UBBLE[160][211]ORT[160][160][160][160][160][160][160][160][160][160][160]"
110 DATA"5.[160][211]HELL[160][211]ORT[160][160][160][160][160][160][160][160][160][160][160][160]","6.[160][200]EAP[160][211]ORT[160][160][160][160][160][160][160][160][160][160][160][160][160]"
120 DATA"7.[160][209]UICKSORT[160][160][160][160][160][160][160][160][160][160][160][160][160]","8.[160][209]UIT[160]TO[160][204]OAD[211]TAR[160][160][160][160][160][160]"
130 DATA"9.[160][208]LAYING[160][215]ITH[160][211]ORTS[160][160][160][160]"
140 FORX=1TO9:READLN(X):NEXT
145 PRINT"[147]":S%=1:FORI=1TO284:READTE$(I):IFVAL(TE$(I))=-2THENS%=S%+1:S(S%)=I+1
146 NEXT
150 DATA 14,14,22,11,10,9,10,,18
160 GOSUB1590:PRINT"";:PRINTTAB(6)"[159][176][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][174]"
170 PRINTTAB(6)"[165][160][160][160][160][160][160][160][160][156][211]ORT[160][196]EMO[160][160][160][160][160][160][160][160][159][167] [159]"
180 PRINTTAB(6)"[165][160][160][160][160][160][160][156][194]Y[160][194]RIAN[160][194]OESE[160][160][160][160][160][159][167] [159]"
190 PRINTTAB(6)"[165][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][167] [159]"
200 PRINTTAB(6)"[165]"MN$(1)"[159][167] [159]"
210 FORX=2TO8:PRINTTAB(6)"[165][154]"MN$(X)"[159][167] [159]":NEXT
220 PRINTTAB(6)"[173][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][189] "
230 PRINTTAB(7)"                           ":SR=1
240 GETA$:IF(A$<>"[145]")AND(A$<>"")AND(A$<>CHR$(13))AND((A$<"1")OR(A$>"9"))THEN240
250 PRINT"[154]";:FORX=1TOSR:PRINT"";:NEXT:PRINTTAB(7)MN$(SR)
260 IFA$=""THENSR=SR+1:IFSR=9THENSR=1
270 IFA$="[145]"THENSR=SR-1:IFSR=0THENSR=8
280 IF(A$>"0")AND(A$<":")THENSR=VAL(A$):GOTO310
290 PRINT"";:FORX=1TOSR:PRINT"";:NEXT:PRINTTAB(7)MN$(SR)
300 IFA$<>CHR$(13)THEN240
310 GOSUB2000:PRINT"[147]":GOSUB2020:PRINT"[147]":GOSUB2010:IFSR<>8THEN360
320 POKE56576,151:POKE648,4:POKE53272,21:PRINT"[147]"
330 OPEN15,8,15,"R0:HELLO CONNECT=HELLO CONNECT":INPUT#15,ER:CLOSE15
340 IFER<>63THENEND
350 F$="HELLO CONNECT":PRINT"[147]LOADF$,8":POKE631,19:POKE632,131:POKE198,2:END
360 POKE53280,2:POKE53272,8:POKE53265,59:POKE53270,216
370 SYS828:POKE53280,6
380 FORY=1TOMX:AR(Y)=INT(RND(0)*160)*4+INT(RND(0)*3)+1
390 X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:NEXT:POKE53280,0
400 AB=0:ONSRGOSUB570,650,740,830,930,1040,1260,400,1470
410 POKE53280,4:POKE198,0:WAIT198,1:GETA$:POKE53280,0
420 POKE53272,18:POKE648,196:POKE53265,27:POKE53270,200
430 GOSUB1590:PRINT""TAB(6)"[159][176][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][163][174]"
440 PRINTTAB(6)"[165][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][167] [145][156]"
450 FORX=1TO(40-LN(SR))/2:PRINT"";:NEXT:PRINTMID$(MN$(SR),4,LN(SR))
460 PRINTTAB(6)"[159][165][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][167] "
470 IF(AB)THENPRINTTAB(6)"[159][165][154][160][160][212]HE[160]SORT[160]WAS[160]ABORTED.[160][160][159][167] ":GOTO500
480 PRINTTAB(6)"[159][165][154][160][160][160][160][160][160]DATA[160]ITEMS[160]SORTED[160][160][159][167] [145]"
490 PRINTTAB(9)"[154]"MID$(STR$(MX),2)
500 PRINTTAB(6)"[159][165][154][160][160][160][212]IME[160]TAKEN:[160][160][160][160][160][160][160][160][160][160][160][159][167] [145][154]"
510 PRINTTAB(24)MID$(T$,3,2)":"MID$(T$,5,2)
520 PRINTTAB(6)"[159][165][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][160][167] "
530 PRINTTAB(6)"[159][165][208]RESS[160]ANY[160]KEY[160]TO[160]CONTINUE[159][167] "
540 PRINTTAB(6)"[159][173][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][164][189] "
550 PRINTTAB(7)"                           "
560 POKE198,0:WAIT198,1:GETA$:GOTO160
570 TI$="000000":FORI=2TOMX:J=I-1:VL=AR(I):REM 1ST LINE OF INSERTION SORT
580 GOSUB1570:IF(AB)THENI=MX:GOTO620
590 IF(VL<AR(J))AND(J>0)THENGOSUB630:J=J-1:GOTO580
600 Y=J+1:X=FNHZ(AR(Y)):POKEFNME(.),0
610 AR(J+1)=VL:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
620 NEXT:T$=TI$:RETURN
630 Y=J+1:X=FNHZ(AR(Y)):POKEFNME(.),0:AR(J+1)=AR(J)
640 X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
650 TI$="000000":REM 1ST LINE OF SELECTION SORT
660 FORI=1TOMX-1:FORJ=MXTOI+1STEP-1:IFAR(J)<AR(I)THENGOSUB690
670 GOSUB1570:IF(AB)THENJ=I+1:I=MX-1
680 NEXT:NEXT:T$=TI$:RETURN
690 Y=I:X=FNHZ(AR(Y)):POKEFNME(.),0
700 Y=J:X=FNHZ(AR(Y)):POKEFNME(.),0
710 TP=AR(I):AR(I)=AR(J):AR(J)=TP
720 Y=I:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
730 Y=J:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
740 TI$="000000":REM 1ST LINE OF DELAYED SELECTION SORT
750 FORI=1TOMX-1:K=I:FORJ=I+1TOMX:IFAR(J)<AR(K)THENK=J
760 GOSUB1570:IF(AB)THENJ=MX:I=MX-1
770 NEXT:GOSUB780:NEXT:T$=TI$:RETURN
780 Y=I:X=FNHZ(AR(Y)):POKEFNME(.),0
790 Y=K:X=FNHZ(AR(Y)):POKEFNME(.),0
800 TP=AR(I):AR(I)=AR(K):AR(K)=TP
810 Y=I:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
820 Y=K:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
830 TI$="000000":BD=MX:REM 1ST LINE OF BUBBLE SORT
840 J=0:FORI=1TOBD-1:IFAR(I)>AR(I+1)THENGOSUB880:J=I
850 GOSUB1570:IF(AB)THENI=BD-1:BD=0
860 NEXT:BD=J:IF(BD<>0)THEN840
870 T$=TI$:RETURN
880 Y=I:X=FNHZ(AR(Y)):POKEFNME(.),0
890 Y=I+1:X=FNHZ(AR(Y)):POKEFNME(.),0
900 TP=AR(I):AR(I)=AR(I+1):AR(I+1)=TP
910 Y=I:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
920 Y=I+1:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
930 TI$="000000":G=INT(MX/2):REM 1ST LINE OF SHELL SORT
940 DN=-1:FORI=1TOMX-G:IFAR(I)>AR(I+G)THENGOSUB990:DN=0
950 GOSUB1570:IF(AB)THENI=MX-G:DN=-1:G=0
960 NEXT:IF(NOT DN)THEN940
970 G=INT(G/2):IFG>0THEN940
980 T$=TI$:RETURN
990 Y=I:X=FNHZ(AR(Y)):POKEFNME(.),0
1000 Y=I+G:X=FNHZ(AR(Y)):POKEFNME(.),0
1010 TP=AR(I):AR(I)=AR(I+G):AR(I+G)=TP
1020 Y=I:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
1030 Y=I+G:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
1040 TI$="000000":REM 1ST LINE OF HEAP SORT
1050 FORI=INT(MX/2)TO1STEP-1:L=I:R=MX:GOSUB1170
1060 GOSUB1570:IF(AB)THENI=1
1070 NEXT:IF(AB)THEN1110
1080 FORI=MX-1TO1STEP-1:GOSUB1120:L=1:R=I:GOSUB1170
1090 GOSUB1570:IF(AB)THENI=1
1100 NEXT
1110 T$=TI$:RETURN
1120 Y=1:X=FNHZ(AR(Y)):POKEFNME(.),0
1130 Y=I+1:X=FNHZ(AR(Y)):POKEFNME(.),0
1140 TP=AR(I+1):AR(I+1)=AR(1):AR(1)=TP
1150 Y=1:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
1160 Y=I+1:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
1170 J=2*L:VL=AR(L)
1180 IFJ>RTHEN1240
1190 IF(J<R)THENIF(AR(J)<AR(J+1))THENJ=J+1
1200 IFVL>=AR(J)THEN1240
1210 Y=L:X=FNHZ(AR(Y)):POKEFNME(.),0:AR(L)=AR(J)
1220 X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
1230 L=J:J=2*J:GOTO1180
1240 Y=L:X=FNHZ(AR(Y)):POKEFNME(.),0:AR(L)=VL
1250 X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
1260 TI$="000000":SL(1)=1:SR(1)=MX:PT=1:REM 1ST LINE OF QUICKSORT
1270 L=SL(PT):R=SR(PT):PT=PT-1
1280 I=L:J=R:VL=AR((L+R)/2)
1290 IFAR(I)<VLTHENI=I+1:GOTO1290
1300 IFAR(J)>VLTHENJ=J-1:GOTO1300
1310 GOSUB1570:IF(AB)THEN1410
1320 IFI<=JTHENGOSUB1420:I=I+1:J=J-1
1330 IFI<=JTHEN1290
1340 IF(J-L)<(R-I)THEN1380:REM PUT LARGEST LIST ON STACK
1350 IFL<JTHENPT=PT+1:SL(PT)=L:SR(PT)=J
1360 L=I:IFL<RTHEN1280
1370 GOTO1400
1380 IFI<RTHENPT=PT+1:SL(PT)=I:SR(PT)=R
1390 R=J:IFL<RTHEN1280
1400 IFPT<>0THEN1270
1410 T$=TI$:RETURN
1420 Y=I:X=FNHZ(AR(Y)):POKEFNME(.),0
1430 Y=J:X=FNHZ(AR(Y)):POKEFNME(.),0
1440 TP=AR(I):AR(I)=AR(J):AR(J)=TP
1450 Y=I:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
1460 Y=J:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
1470 TI$="000000":REM 1ST LINE FOR PLAYING WITH SORTS
1480 FORI=1TOMX-1:FORJ=I+1TOMX:IFAR(J)<AR(I)THENGOSUB1510
1490 GOSUB1570:IF(AB)THENJ=I+1:I=MX-1
1500 NEXT:NEXT:T$=TI$:RETURN
1510 Y=I:X=FNHZ(AR(Y)):POKEFNME(.),0
1520 Y=J:X=FNHZ(AR(Y)):POKEFNME(.),0
1530 TP=AR(I):AR(I)=AR(J):AR(J)=TP
1540 Y=I:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL
1550 Y=J:X=FNHZ(AR(Y)):CL=FNCL(AR(Y))*FNPS(AR(Y)):POKEFNME(.),CL:RETURN
1560 T$=TI$:RETURN
1570 GETA$:IFA$="Q"THENAB=-1
1580 RETURN
1590 PRINT"[154][147]";:FORX=1TO24:PRINT"                                       [157][148] "
1600 NEXT:PRINT"                                       [157][148] ";:RETURN
1999 REM STASH FONT
2000 JJ=51200+8*32:FORI=0TO7:F(I)=PEEK(JJ+I):POKEJJ+I,0:NEXT:RETURN
2009 REM REPLACE FONT
2010 JJ=51200+8*32:FORI=0TO7:POKEJJ+I,F(I):NEXT:RETURN
2019 REM DISPLAY TEXT
2020 I=S(SR):PRINT"[147][159]":IFSR>7THENRETURN
2030 PRINT""TE$(I):I=I+1:IFVAL(TE$(I))>-1THEN2030
2040 POKE198,0:WAIT198,15:POKE198,0
2050 IFVAL(TE$(I))=-2THENRETURN
2060 I=I+1:PRINT"[147]":GOTO2030
5000 DATA"       [201] [206] [211] [197] [210] [212] [201] [207] [206]   [211] [207] [210] [212]"
5010 DATA""
5020 DATA"    [212]HE BASIC IDEA FOR INSERTION"
5030 DATA"SORTING IS LIKE BEING DEALT A HAND OF"
5040 DATA"CARDS.  [208]ICK THEM UP ONE AT A TIME,"
5050 DATA"AND PLACE EACH INTO ITS CORRECT"
5060 DATA"POSITION RELATIVE TO THE CARDS YOU"
5070 DATA"HAVE ALREADY PICKED UP.",-1
5080 DATA""
5090 DATA"  FOR I = 2 TO SIZE"
5100 DATA"     J = I - 1"
5110 DATA"     VALUE = ARRAY(I)"
5120 DATA"     WHILE (VALUE<ARRAY(J)) AND"
5130 DATA"(J>0)"
5140 DATA"        ARRAY(J+1) = ARRAY(J)"
5150 DATA"        J = J - 1"
5160 DATA"     END WHILE"
5170 DATA"     ARRAY(J+1) = VALUE"
5180 DATA"  END FOR"
5190 DATA-1
5200 DATA"    [207]NE ADDITIONAL POINT HERE IS"
5210 DATA"THAT YOU ALSO HAVE TO MAKE SURE THAT"
5220 DATA"YOU DON'T GO BEYOND THE FRONT OF THE"
5230 DATA"ARRAY.  [217]OU CAN DO THIS EITHER BY"
5240 DATA"PUTTING AN EXTRA CONDITION INTO THE"
5250 DATA"WHILE LOOP, SUCH AS THE 'AND J>0'"
5260 DATA"CONDITION, OR BY SETTING THE VALUE AT"
5270 DATA"ARRAY(0) TO BE SOME VALUE SMALLER"
5280 DATA"THAN ANY OTHER VALUE IN THE ARRAY."
5290 DATA""
5300 DATA"    [197]VEN THOUGH THIS IS A RELATIVELY"
5310 DATA"SLOW ALGORITHM, IT IS ESPECIALLY"
5320 DATA"USEFUL IF THE LIST YOU ARE SORTING"
5330 DATA"HAS ALREADY BEEN SORTED PREVIOUSLY,"
5340 DATA"AND YOU ONLY HAVE A FEW ITEMS ADDED"
5350 DATA"TO THE END.  [217]OU ONLY THEN NEED TO"
5360 DATA"INSERT THESE FEW ITEMS INTO THE"
5370 DATA"ALREADY SORTED LIST, AND YOU ARE"
5380 DATA"DONE."
5390 DATA-2
5410 DATA" -----------------------------"
5420 DATA"  [211] [197] [204] [197] [195] [212] [201] [207] [206]   [211] [207] [210] [212]"
5430 DATA" -----------------------------"
5440 DATA""
5450 DATA"     [212]HE IDEA HERE IS TO COMPARE EACH"
5460 DATA"ITEM WITH ALL OF THE OTHERS IN TURN,"
5470 DATA"SWITCHING THEM IF THEY ARE OUT OF"
5480 DATA"  ORDER."
5490 DATA"  "
5500 DATA"    FOR I = 1 TO SIZE - 1"
5510 DATA"       FOR J = SIZE TO I+1 STEP -1"
5520 DATA"          IF ARRAY(J) < ARRAY(I) THEN"
5530 DATA"             TEMP = ARRAY(I)"
5540 DATA"             ARRAY(I) = ARRAY(J)"
5550 DATA"             ARRAY(J) = TEMP"
5560 DATA"          END IF"
5570 DATA"       END FOR"
5580 DATA"    END FOR"
5590 DATA-1
5600 DATA"    [206]OTICE HERE THAT THE INNER LOOP"
5610 DATA"GOES BACKWARD RELATIVE TO THE OUTER"
5620 DATA"LOOP.  [201]'VE FOUND THAT THIS HELPS TO"
5630 DATA"IMPROVE THE SPEED OF THE SORT.  [201]F"
5640 DATA"YOU WOULD LIKE TO SEE WHY, [201] HAVE"
5650 DATA"'HIDDEN' A COPY OF THE OTHER SORT IN"
5660 DATA"THE DEMO PROGRAM.  [193]T THE MENU TYPE"
5670 DATA"'9', EVEN THOUGH IT DOES NOT APPEAR"
5680 DATA"IN THE LIST.  [206]OTICE AS THE SORT"
5690 DATA"PROGRESSES THAT A 'WALL' BEGINS TO"
5700 DATA"APPEAR.  [212]HE SMALLEST ITEM REMAINING"
5710 DATA"MUST PASS THROUGH ALMOST EVERY ITEM"
5720 DATA"IN THE WALL BEFORE IT MAKES IT TO ITS"
5730 DATA"FINAL POSITION.  [200]OWEVER, THE NUMBER"
5740 DATA"IS MUCH REDUCED WHEN THE INNER LOOP"
5750 DATA"IS IN THE REVERSE ORDER."
5760 DATA-2
5780 DATA" -----------------------------------"
5790 DATA"  [196] [197] [204] [193] [217] [197] [196]   [211] [197] [204] [197] [195] [212] [201] [207] [206]"
5800 DATA" -----------------------------------"
5810 DATA""
5820 DATA"    [212]HE IDEA HERE IS SIMILAR TO THAT"
5830 DATA"OF NORMAL SELECTION.  [200]OWEVER, ONLY"
5840 DATA"THE SMALLEST ITEM IS SWITCHED."
5850 DATA"  "
5860 DATA"    FOR I = 1 TO SIZE - 1"
5870 DATA"       K = I"
5880 DATA"       FOR J = I+1 TO SIZE"
5890 DATA"          IF ARRAY(J) < ARRAY(K) THEN"
5900 DATA"             K = J"
5910 DATA"          END IF"
5920 DATA"       END FOR"
5930 DATA"       TEMP = ARRAY(I)"
5940 DATA"       ARRAY(I) = ARRAY(K)"
5950 DATA"       ARRAY(K) = TEMP"
5960 DATA"    END FOR"
5970 DATA-1
5980 DATA"     [206]OTICE THAT THIS SORT IS MUCH"
5990 DATA"FASTER THAN NORMAL SELECTION.  [[197]VEN"
6000 DATA"CONSIDERING THE OVERHEAD OF"
6010 DATA"MAINTAINING THE GRAPHIC SCREEN IT IS"
6020 DATA"STILL FASTER.]  [212]HIS IS BECAUSE,"
6030 DATA"WHILE THE NUMBER OF COMPARISONS"
6040 DATA"REMAINS THE SAME, ONLY ONE SWITCH IS"
6050 DATA"MADE EACH TIME."
6060 DATA-2
6080 DATA" -----------------------"
6090 DATA"  [194] [213] [194] [194] [204] [197]   [211] [207] [210] [212]"
6100 DATA" -----------------------"
6110 DATA""
6120 DATA"     [212]HIS SORT IS PERHAPS THE"
6130 DATA"FAVORITE OF THEM ALL FOR MOST"
6140 DATA"PROGRAMMERS.  [197]ACH NEIGHBORING PAIR"
6150 DATA"IS COMPARED, AND SWITCHED IF THEY ARE"
6160 DATA"OUT OF ORDER."
6170 DATA""
6180 DATA"  BOUND = SIZE"
6190 DATA"  WHILE BOUND <> 0"
6200 DATA"     J = 0     FOR I = 1 TO BOUND -1"
6210 DATA"        IF ARRAY(I) > ARRAY(I+1) THEN"
6220 DATA"           TEMP = ARRAY(I)"
6230 DATA"           ARRAY(I) = ARRAY(I+1)"
6240 DATA"           ARRAY(I+1) = TEMP"
6250 DATA"           J = I"
6260 DATA"        END IF"
6270 DATA"     END FOR"
6280 DATA"  END WHILE"
6290 DATA-1
6300 DATA"     [212]HIS IS ALSO THE SLOWEST OF ALL"
6310 DATA"OF THE SORTS IN THE DEMO."
6320 DATA-2
6340 DATA" ---------------------"
6350 DATA"  [211] [200] [197] [204] [204]   [211] [207] [210] [212]"
6360 DATA" ---------------------"
6370 DATA" "
6380 DATA"     [212]HE BASIC IDEA HERE IS TO SPEED"
6390 DATA"UP THE SORTING PROCESS BY COMPARING"
6400 DATA"ITEMS WITH OTHER ITEMS FURTHER DOWN"
6410 DATA"THE LIST."
6420 DATA-1
6430 DATA" D = INT(SIZE/2)"
6440 DATA" REPEAT"
6450 DATA"    REPEAT"
6460 DATA"       DONE = TRUE"
6470 DATA"       FOR I = 1 TO SIZE-D"
6480 DATA"          IF ARRAY(I)>ARRAY(I+D) THEN"
6490 DATA"             TEMP = ARRAY(I)"
6500 DATA"             ARRAY(I) = ARRAY(I+D)"
6510 DATA"             ARRAY(I+D) = TEMP"
6520 DATA"             DONE = FALSE"
6530 DATA"          END IF"
6540 DATA"       END FOR"
6550 DATA"    UNTIL DONE"
6560 DATA"    D = INT(D/2)"
6570 DATA" UNTIL D=0"
6580 DATA-2
6610 DATA" -------------------"
6620 DATA"  [200] [197] [193] [208]   [211] [207] [210] [212]"
6630 DATA" -------------------"
6640 DATA""
6650 DATA"    [212]HE [200]EAP SORT IS PROBABLY THE"
6660 DATA"STRANGEST OF ALL THE SORTS IN THE"
6670 DATA"DEMO.  [194]EFORE [201] CAN DESCRIBE IT TO"
6680 DATA"YOU, FIRST [201] MUST DEFINE WHAT A HEAP"
6690 DATA"IS.  [193] HEAP IS A BINARY TREE WHERE"
6700 DATA"THE VALUE OF THE ITEM AT ANY POINT IS"
6710 DATA"LARGER THAN THE VALUE AT EITHER"
6720 DATA"BRANCH. [208]UTTING THE LIST INTO A HEAP"
6730 DATA"IS USEFUL FOR SORTING FOR THESE"
6740 DATA"REASONS:  IT CAN BE DONE VERY"
6750 DATA"QUICKLY, AND AT ANY POINT IN TIME WE"
6760 DATA"HAVE ISOLATED THE LARGEST ITEM IN THE"
6770 DATA"ARRAY."
6780 DATA-1
6790 DATA"     FOR I = INT(SIZE/2) TO 1 STEP-1"
6800 DATA"        LEFT = I"
6810 DATA"        RIGHT = SIZE"
6820 DATA"        GOSUB [211][201][198][212]"
6830 DATA"     NEXT"
6840 DATA"     FOR I = SIZE - 1 TO 1 STEP -1"
6850 DATA"        TEMP = ARRAY(I+1)"
6860 DATA"        ARRAY(I+1) = ARRAY(1)"
6870 DATA"        ARRAY(1) = TEMP"
6880 DATA"        LEFT = 1"
6890 DATA"        RIGHT = I"
6900 DATA"        GOSUB [211][201][198][212]"
6910 DATA"     NEXT"
6920 DATA""
6930 DATA"WHERE THE PROCEDURE [211][201][198][212] IS DEFINED...",-1
6950 DATA"    J = 2 * LEFT"
6960 DATA"    VALUE = ARRAY(LEFT)"
6970 DATA"    LOOP
6980 [131]"       IF J > RIGHT THEN"
6990 [131]"          ARRAY(LEFT) = VALUE"
7000 [131]"          RETURN"
7010 [131]"       END IF"
7020 [131]"       IF J < RIGHT THEN"
7030 [131]"        IF ARRAY(J) < ARRAY(J+1) THEN"
7040 [131]"             J = J + 1"
7050 [131]"          END IF"
7060 [131]"       END IF"
7070 [131]"       IF VALUE >= ARRAY(J) THEN"
7080 [131]"          ARRAY(LEFT) = VALUE"
7090 [131]"          RETURN"
7100 [131]"       END IF"
7110 [131]"       ARRAY(LEFT) = ARRAY(J)"
7120 [131]"       LEFT = J"
7130 [131]"       J = 2 * J"
7140 [131]"    END LOOP"
7150 [131]-1
7160 [131]"    RIGHT$NITIALLY, THE LIST IS ORGANIZED"
7170 [131]"INTO A HEAP.  (null)HEN, THE FIRST ITEM IS"
7180 [131]"SWITCHED WITH THE LAST, THE LAST ITEM"
7190 [131]"IS REMOVED FROM THE HEAP, AND THEN"
7200 [131]"THE HEAP IS RESTORED."
7210 [131]""
7220 [131]"    (null)OTICE HERE THAT OFTEN AS THE"
7230 [131]"SPEED OF THE SORTING ALGORITHM"
7240 [131]"INCREASES, SO DOES THE COMPLEXITY OF"
7250 [131]"THE ALGORITHM."
7260 [131]-2
7280 [131]" -------------------"
7290 [131]"  (null) (null) RIGHT$ LEN (null) (null) (null) (null) (null)"
7300 [131]" -------------------"
7310 [131]""
7320 [131]"    (null)HIS IS THE FASTEST KNOWN"
7330 [131]"ALGORITHM FOR SORTING A LIST.  RIGHT$T"
7340 [131]"EMPLOYS A DIVIDE-AND-CONQUER"
7350 [131]"ALGORITHM, SEPARATING THE LIST INTO"
7360 [131]"TWO SMALLER LISTS, EACH OF WHICH IS"
7370 [131]"THEN SORTED."
7380 [131]""
7390 [131]"     LEFT$ERE WE HAVE TO DEFINE A STACK,"
7400 [131]"WHICH IS USED TO KEEP TRACK OF THE"
7410 [131]"PARTS OF THE LIST WE HAVE NOT SORTED"
7420 [131]"YET."
7430 [131]-1
7440 [131]"  STACK.LEFT(1) = 1"
7450 [131]"  STACK.RIGHT(1) = SIZE"
7460 [131]"  POINT = 1"
7470 [131]"  REPEAT"
7480 [131]"     LEFT = STACK.LEFT(POINT)"
7490 [131]"     RIGHT = STACK.RIGHT(POINT)"
7500 [131]"     POINT = POINT - 1"
7510 [131]"     I = LEFT"
7520 [131]"     REPEAT"
7530 [131]"     J = RIGHT"
7540 [131]"        VALUE = ARRAY((LEFT+RIGHT)/2)"
7550 [131]"        REPEAT"
7560 [131]"           WHILE ARRAY(I) < VALUE"
7570 [131]"              I = I + 1"
7580 [131]"           END WHILE"
7590 [131]"           WHILE ARRAY(J) > VALUE"
7600 [131]"              J = J - 1"
7610 [131]"           END WHILE",-1
7620 [131]"           IF I <= J THEN"
7630 [131]"              TEMP = ARRAY(I)"
7640 [131]"              ARRAY(I) = ARRAY(J)"
7650 [131]"              ARRAY(J) = TEMP"
7660 [131]"              I = I + 1"
7670 [131]"              J = J - 1"
7680 [131]"           END IF"
7690 [131]"        UNTIL I > J"
7700 [131]"        IF LEFT < J THEN"
7710 [131]"           POINT = POINT + 1"
7720 [131]"           STACK.LEFT(POINT) = LEFT"
7730 [131]"           STACK.RIGHT(POINT) = J"
7740 [131]"        END IF"
7750 [131]"        LEFT = I"
7760 [131]"     UNTIL LEFT >= RIGHT"
7770 [131]"  UNTIL POINT = 0"
7780 [131]"  "
7790 [131]-1
7800 [131]"    (null)NE OTHER CONSIDERATION THAT IS"
7810 [131]"NOT IN THIS BASIC ALGORITHM IS THAT"
7820 [131]"THE STACK MAY EVENTUALLY OVERFLOW. "
7830 [131]"LEFT$OWEVER, IF WE WERE TO ALWAYS PLACE"
7840 [131]"THE LARGEST SECTION ONTO THE STACK,"
7850 [131]"THEN WE CAN GUARANTEE THAT EVERYTHING"
7860 [131]"WILL FIT.  (null)HIS MODIFICATION WAS MADE"
7870 [131]"TO THE DEMO PROGRAM."
7880 [131]-2