1 REM Ins{nt av 3018
10 REM +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
15 REM ++ SORTERINGSTEST - SE PERSONDATORN NR 6 SEPTEMBER 1984 ++
20 REM ++ Anpassat och modifierat f|r ABC-80 ++
25 REM ++ Av 3018 Sigvard Nilsson den 23 : e September 1984 ++
30 REM ++ Program som pr|var hur effektivt olika ++
35 REM ++ sorteringsalgoritmer kan utf|ra en sortering. ++
40 REM +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
45 ; CHR$(12%) : ONERRORGOTO 45 : N%=0%
50 ; ' Sorteringstest.'
55 ; ' =============='
60 ; : ; 'Med detta program kan Du direkt unders|ka skillnaden '
65 ; : ; 'i snabbhet melllan olika sorteringsalgoritmer.'
70 ; : ; 'Programmet tar sj{lv tid p} sorteringsproceduren.'
75 ; : ; : ; 'F|rst skapas ett antal slumpvis bildade "ord" '
80 ; : ; 'Hur m}nga ord skall sorteras ? (Max 600)'; : INPUT N%
85 DIM A$(N%)=7%,B$(N%)=7%
90 DEFFNU(I)=INT(I)-(I<>INT(I))
95 REM ++++++++++++++++++++++++++++
100 REM ++ Bilda ord att sortera ++
105 REM ++++++++++++++++++++++++++++
110 ; : ; 'V [ N T A ! Ordf|rr}det byggs upp.'
115 FOR I%=1% TO N% : A$="" : A$=CHR$(RND*28%+65%) : FOR J%=1% TO RND*4%+2% : A$=A$+CHR$(RND*28%+97%) : NEXT J%
120 A$(I%)=A$ : B$(I%)=A$ : NEXT I% : ;
125 ; : ; 'K L A R T !' : ; CHR$(7%)
130 FOR F=1 TO 2000 : NEXT F : ; CHR$(12%)
135 ; ' S O R T E R I N G .'
140 ; ' =================='
145 ; : ; 'Nu sorteras';N%;' ord'
150 ; 'V{lj metod genom att ange en siffra'
155 ; : ; ' 1. BUBBLE-sortering'
160 ; : ; ' 2. URVALS-sortering'
165 ; : ; ' 3. DELAYED REPLACEMENT-sortering'
170 ; : ; ' 4. BATCHER-sortering'
175 ; : ; ' 5. SHELL-METZNER-sortering'
180 ; : ; ' 6. QUICKSORT.'
185 ; : ; 'V[LJ METOD (1-6) '; : INPUT G%
190 IF G%<1% OR G%>6% THEN 185
195 ; : ; 'S O R T E R I N G P ] G ] R !'
200 REM ++++++++++++++++++++++++
205 REM ++ KLOCKAN NOLLST[LLS ++
210 REM ++++++++++++++++++++++++
215 POKE 65008%,0%,0%,0%
220 REM
225 ; CUR(G%*2+5%,7%)CHR$(127%)
230 ON G% GOSUB 250,310,410,490,560,650
235 GOSUB 920
240 GOTO 950
245 REM +++++++++++++++++++++
250 REM ++ BUBBLESORTERING ++
255 REM +++++++++++++++++++++
260 FOR I%=1% TO N%-1%
265 FOR J%=I%+1% TO N%
270 IF B$(I%)=T$ 360
350 T$=B$(J%)
355 K%=J%
360 J%=J%+1%
365 IF J%<=N% 345
370 T$=B$(K%)
375 B$(K%)=B$(I%)
380 B$(I%)=T$
385 I%=I%+1%
390 IF I%B$(J2%) 455
450 J2%=M2%
455 M2%=M2%+1%
460 IF M2%<=N% 445
465 IF L2%=J2% 425
470 T$=B$(J2%)
475 B$(J2%)=B$(L2%)
480 B$(L2%)=T$
485 GOTO 425
490 REM +++++++++++++++++++++++
495 REM ++ BATCHER-SORTERING ++
500 REM +++++++++++++++++++++++
505 T%=FNU(LOG(N%)/LOG(2)) : P%=INT(2^(T%-1%))
510 Q%=INT(2^(T%-1%)) : R%=0% : D%=P%
515 S%=P% OR R% : G%=N%-D%-1% : FOR K%=R% TO G% STEP S%*2% : H%=K%+S%-1% : IF G%B$(J%+D%) THEN T$=B$(J%) : B$(J%)=B$(J%+D%) : B$(J%+D%)=T$
530 NEXT I%
535 NEXT K%
540 IF Q%<>P% THEN D%=Q%-P% : Q%=Q%/2 : R%=P% : GOTO 515
545 P%=INT(P%/2%) : IF P% 510
550 RETURN
555 REM ++++++++++++++++++++++++++++++
560 REM ++ SHELL-METZNER-SORTERING ++
565 REM ++++++++++++++++++++++++++++++
570 M1%=N%
575 M1%=INT(M1%/2%)
580 IF M1%=0% RETURN
585 K7%=N%-M1%
590 J1%=1%
595 I1%=J1%
600 L1%=I1%+M1%
605 IF B$(I1%)<=B$(L1%) 635
610 T$=B$(I1%)
615 B$(I1%)=B$(L1%)
620 B$(L1%)=T$
625 I1%=I1%-M1%
630 IF I1%>=1% 600
635 J1%=J1%+1%
640 IF J1%>K7% 575
645 GOTO 595
650 REM ++++++++++++++++++++
655 REM ++ QUICKSORTERING ++
660 REM ++++++++++++++++++++
665 M3%=1%
670 P%(M3%)=1%
675 W%(M3%)=N%
680 L3%=1%
685 R3%=N%
690 IF (R3%-L3%)<9% 840
695 I3%=L3%
700 J3%=R3%
705 IF B$(I3%)>B$(J3%) 755
710 J3%=J3%-1%
715 IF J3%>I3% 705
720 J3%=J3%+1%
725 M3%=M3%+1%
730 IF (I3%-L3%)<(R3%-J3%) 820
735 P%(M3%)=L3%
740 W%(M3%)=I3%
745 L3%=J3%
750 GOTO 690
755 T$=B$(J3%)
760 B$(J3%)=B$(I3%)
765 B$(I3%)=T$
770 GOTO 780
775 IF B$(J3%)I3% 775
790 J3%=J3%+1%
795 GOTO 725
800 T$=B$(J3%)
805 B$(J3%)=B$(I3%)
810 B$(I3%)=T$
815 GOTO 710
820 P%(M3%)=J3%
825 W%(M3%)=R3%
830 R3%=I3%
835 GOTO 690
840 IF (R3%-L3%+1)=1% 890
845 FOR I3%=(L3%+1%) TO R3%
850 FOR J3%=L3% TO (I3%-1%)
855 J9=I3%-J3%+L3%-1%
860 IF B$(J9)<=B$(J9+1%) 885
865 T$=B$(J9)
870 B$(J9)=B$(J9+1)
875 B$(J9+1%)=T$
880 NEXT J3%
885 NEXT I3%
890 L3%=P%(M3%)
895 R3%=W%(M3%)
900 M3%=M3%-1%
905 IF M3%=0% RETURN
910 GOTO 690
915 REM ++++++++++++++++++++++++++++++++
920 REM ++ KLOCKAN L[SES - TIDTAGNING ++
925 REM ++++++++++++++++++++++++++++++++
930 T=(20*(255% XOR PEEK(-528%))+5120*(255% XOR PEEK(-527%))+1.31072E+6*(255% XOR PEEK(-526%)))/1000
935 ; CHR$(12%)CUR(8,20)'Sorteringen tog :'
940 ; CUR(10%,20%)'TIME ';T;' SEKUNDER'CHR$(7)
945 REM
950 REM ++++++++++++++++++++++
955 REM ++ VISUELL KONTROLL ++
960 REM ++++++++++++++++++++++
965 ; CUR(14%,20%)'Vill Du se p} de ord som testats?'
970 ; CUR(16%,20%)'Tryck i s} fall p} tangent'; : GET D$ : ; CHR$(12%)
975 ; ,'Osorterat:',,'Sorterat:'
980 ; ,'=========',,'==========' : ;
985 FOR I%=1% TO N% : ; ,A$(I%),,B$(I%)
990 E%=E%+1%
995 IF E%=15% THEN ; : ; ,'Tryck tangent'; : GET D$ : E%=0% : ; CHR$(12%) : ; ,'Osorterat:',,'Sorterat:'
1000 IF E%=0% THEN ; ,'==========',,'==========' : ;
1005 NEXT I%
1010 END