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%)<B$(J%) 290
275 T$=B$(I%)
280 B$(I%)=B$(J%)
285 B$(J%)=T$
290 NEXT J%
295 NEXT I%
300 RETURN 
305 REM +++++++++++++++++++++
310 REM ++ URVALSSORTERING ++
315 REM +++++++++++++++++++++
320 I%=1%
325 GOTO 390
330 K%=I%
335 T$=B$(I%)
340 J%=I%+1%
345 IF B$(J%)>=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%<N% 330
395 RETURN 
400 REM 
405 REM +++++++++++++++++++++++++++++++++++
410 REM ++ DELAYED REPLACEMENT-SORTERING ++
415 REM +++++++++++++++++++++++++++++++++++
420 J2%=0% : M2%=0% : L2%=0%
425 L2%=L2%+1%
430 IF L2%=N% RETURN 
435 J2%=L2%
440 M2%=J2%+1%
445 IF B$(M2%)>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%<H% THEN H%=G%
520 FOR I%=K% TO H% : J%=I%+1%
525 IF B$(J%)>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%)<B$(I3%) 800
780 I3%=I3%+1%
785 IF 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