10 GRAPHICS 0 20 MAXVALS=1000:DIM VALUES(MAXVALS):DIM STACK(1024):SP=0:COUNT=0 30 INTROS=0:INSERTS=0:HEAPS=0:DIM INFILE$(11):INFILE$="D:INPUT.TXT":DIM OUTFILE$(12):OUTFILE$="D:OUTPUT.TXT" 40 PRINT "½½½½½ÉÎÔÒÏÓÏÒÔ ÁÔÁÒÉ ÂÁÓÉÃ½½½½½" 50 GOSUB 1000 60 GOSUB 8000 70 GOSUB 2000 80 PRINT "½½½½½½½½½½ÒÕÎ ÃÏÍÐÌÅÔÅ½½½½½½½½½½" 90 PRINT "INTROSORT TOOK ";ELAPSED;" SECONDS." 100 PRINT "================================" 110 PRINT "SORT CALLED | TIMES" 120 PRINT "------------+-------------------" 130 PRINT "INTRO | ";INTROS 140 PRINT "INSERTION | ";INSERTS 150 PRINT "HEAP | ";HEAPS 160 PRINT "================================" 999 END 1000 REM ½½½ÌÏÁÄ ÆÉÌÅ½½½ 1010 PRINT "READING INPUT FILE..."; 1020 DIM L$(80) 1030 OPEN #1,4,0,INFILE$ 1040 TRAP 1100 1050 INPUT #1,L$ 1060 IF L$="" THEN GOTO 1040 1070 VALUES(COUNT)=VAL(L$) 1080 COUNT=COUNT+1 1090 GOTO 1040 1100 CLOSE #1 1110 TRAP 65535 1120 PRINT "DONE." 1130 RETURN 1999 REM ½½½½½½½½½½½½½½½ 2000 REM ½½½ÓÁÖÅ ÆÉÌÅ½½½ 2010 PRINT "WRITING OUTPUT FILE..."; 2020 OPEN #1,8,0,OUTFILE$ 2030 FOR I=0 TO COUNT-1 2040 PRINT #1,STR$(VALUES(I)) 2050 NEXT I 2060 CLOSE #1 2070 PRINT "DONE." 2080 RETURN 2999 REM ½½½½½½½½½½½½½½½ 3000 REM ½½½ÓÉÆÔ ÄÏ×Î½½½ 3010 GOSUB 9020:EINDEX=STACKVAL 3020 GOSUB 9020:SINDEX=STACKVAL 3030 GOSUB 9020:RINDEX=STACKVAL 3040 CHILD=SINDEX+2*(RINDEX-SINDEX)+1 3050 IF CHILD>=EINDEX THEN RETURN 3060 IF CHILD+1>=EINDEX THEN GOTO 3090 3070 IF VALUES(CHILD)>=VALUES(CHILD+1) THEN GOTO 3090 3080 CHILD=CHILD+1 3090 IF VALUES(RINDEX)>=VALUES(CHILD) THEN RETURN 3100 TEMP=VALUES(CHILD) 3110 VALUES(RINDEX)=VALUES(CHILD) 3120 VALUES(CHILD)=TEMP 3130 RINDEX=CHILD 3140 GOTO 3040 3999 REM ½½½½½½½½½½½½½½½ 4000 REM ½½½ÈÅÁÐÓÏÒÔ½½½ 4010 HEAPS=HEAPS+1 4020 FOR ROOT=SINDEX+INT((EINDEX-SINDEX)/2)-1 TO SINDEX STEP -1 4030 STACKVAL=ROOT:GOSUB 9010 4040 STACKVAL=SINDEX:GOSUB 9010 4050 STACKVAL=EINDEX:GOSUB 9010 4060 GOSUB 3000 4070 NEXT ROOT 4080 FOR LINDEX=EINDEX-1 TO SINDEX+1 STEP -1 4090 TEMP=VALUES(SINDEX) 4100 VALUES(SINDEX)=VALUES(LINDEX) 4110 VALUES(LINDEX)=TEMP 4120 STACKVAL=SINDEX:GOSUB 9010 4130 STACKVAL=SINDEX:GOSUB 9010 4140 STACKVAL=LINDEX:GOSUB 9010 4150 GOSUB 3000 4160 NEXT LINDEX 4170 RETURN 4999 REM ½½½½½½½½½½½½½½ 5000 REM ½½½ÉÎÓÅÒÔÉÏÎÓÏÒÔ½½½ 5010 INSERTS=INSERTS+1 5020 FOR INDEX=SINDEX TO EINDEX-1 5030 VALUE=VALUES(INDEX) 5040 POS=INDEX-1 5050 IF POSVALUE THEN GOTO 5070 5060 GOTO 5100 5070 VALUES(POS+1)=VALUES(POS) 5080 POS=POS-1 5090 GOTO 5050 5100 VALUES(POS+1)=VALUE 5110 NEXT INDEX 5120 RETURN 5999 REM ½½½½½½½½½½½½½½½½½½½ 6000 REM ½½½ÐÁÒÔÉÔÉÏÎ½½½ 6010 GOSUB 9020:EINDEX=STACKVAL 6020 GOSUB 9020:SINDEX=STACKVAL 6030 LEFT=SINDEX 6040 RIGHT=EINDEX-1 6050 PIVOT=VALUES(SINDEX+(EINDEX-SINDEX)/2) 6060 IF LEFT=PIVOT THEN GOTO 6100 6090 LEFT=LEFT+1:GOTO 6080 6100 IF VALUES(RIGHT)<=PIVOT THEN GOTO 6120 6110 RIGHT=RIGHT-1:GOTO 6100 6120 IF LEFT>RIGHT THEN GOTO 6060 6130 TEMP=VALUES(LEFT) 6140 VALUES(LEFT)=VALUES(RIGHT) 6150 VALUES(RIGHT)=TEMP 6160 LEFT=LEFT+1 6170 RIGHT=RIGHT-1 6180 GOTO 6060 6190 PART=LEFT 6200 RETURN 6999 REM ½½½½½½½½½½½½½½½ 7000 REM ½½½ÉÎÔÒÏÓÏÒÔ½½½ 7010 INTROS=INTROS+1 7020 GOSUB 9020:MAXDEPTH=STACKVAL 7030 GOSUB 9020:EINDEX=STACKVAL 7040 GOSUB 9020:SINDEX=STACKVAL 7050 LENGTH=EINDEX-SINDEX 7060 IF LENGTH<=1 THEN RETURN 7070 IF LENGTH<16 THEN GOTO 7210 7080 IF MAXDEPTH<0 THEN GOTO 7220 7090 STACKVAL=SINDEX:GOSUB 9010 7100 STACKVAL=EINDEX:GOSUB 9010 7110 GOSUB 6000 7120 STACKVAL=PART:GOSUB 9010 7130 STACKVAL=EINDEX:GOSUB 9010 7140 STACKVAL=MAXDEPTH-1:GOSUB 9010 7150 STACKVAL=SINDEX:GOSUB 9010 7160 STACKVAL=PART:GOSUB 9010 7170 STACKVAL=MAXDEPTH-1:GOSUB 9010 7180 GOSUB 7000 7190 GOSUB 7000 7200 RETURN 7210 GOSUB 5000:RETURN 7220 GOSUB 4000:RETURN 7999 REM ½½½½½½½½½½½½½½½ 8000 REM ½½½ÐÅÒÆÏÒÍ ÓÏÒÔ½½½ 8010 PRINT "SORTING ELEMENTS..."; 8020 LOGVAL=COUNT:GOSUB 9050 8030 MAXDEPTH=LOGNUM*2 8040 STACKVAL=0:GOSUB 9010 8050 STACKVAL=COUNT:GOSUB 9010 8060 STACKVAL=MAXDEPTH:GOSUB 9010 8070 STIME=(PEEK(18)*65536+PEEK(19)*256+PEEK(20))/60 8080 GOSUB 7000 8090 ETIME=TIMER 8100 PRINT "DONE." 8110 ELAPSED=(PEEK(18)*65536+PEEK(19)*256+PEEK(20))/60 8120 IF ELAPSED<0 THEN ELAPSED=ELAPSED+86400 8130 RETURN 8999 REM ½½½½½½½½½½½½½½½½½½ 9000 REM ½½½ÓÔÁÃË ÓÕÂÒÏÕÔÉÎÅÓ½½½ 9010 STACK(SP)=STACKVAL:SP=SP+1:RETURN 9020 SP=SP-1:STACKVAL=STACK(SP):RETURN 9030 REM ½½½½½½½½½½½½½½½½½½½½½½½ 9050 REM ½½½ÌÏÇ²½½½ 9060 LOGNUM=0 9070 IF LOGVAL<=1 THEN RETURN 9080 LOGVAL=LOGVAL/2 9090 LOGNUM=LOGNUM+1 9100 GOTO 9070 9199 REM ½½½½½½½½½½