1 REM Ins{nd av Leopold Lundstr|m <2694>    1986-10-23 12.34.54 (DUMP)
10 REM ++++++++++++++++++++++++
11 REM Subrutiner  SORTERING
12 REM Av Anders Sandberg <4104>
13 REM
14 REM Program     SORT4104.BAS
15 REM Inmatade efter artikel i
16 REM ABC-bladet 3.86 s 39 ff
17 REM av L Lundstr|m <2694>
18 REM
19 REM Prog stl ... 5.8 Kbyte
20 REM Variabler .. 0.4 Kbyte
21 REM
22 REM Testad p} f|ljande maskiner
23 REM ABC80 11273 av <2694> 86-10-21
24 REM Speciella tillbeh|r
25 REM Utbyggt minne ..(Nej)
26 REM
27 REM Anv{nder :
28 REM
29 REM ------------------------------
30 REM Beskrivning :
31 REM Se ABC-bladet
32 REM
1000 REM
1010 REM Falsk bubblesort
1020 REM
1030 FOR I%=1% TO N%-1% : T$=B$(I%) : FOR J%=I%+1% TO N%
1040 IF T$>B$(J%) B$(I%)=B$(J%) : B$(J%)=T$ : T$=B$(I%)
1050 NEXT J% : NEXT I%
1060 RETURN
1100 REM
1110 REM Bubblesort KNUTH 5.2.2 B
1120 REM
1130 J%=N%
1140 R%=J% : J%=0 : FOR I%=1% TO R%-1%
1150 IF B$(I%)>B$(I%+1%) T$=B$(I%) : B$(I%)=B$(I%+1%) : B$(I%+1%)=T$ : J%=I%
1160 NEXT I% : IF J% THEN 1140 ELSE RETURN
1200 REM
1210 REM Bubblesort KNUTH 5.2.2 B
1220 REM
1230 R%=N% : J%=1%
1240 L%=J% : J%=0% : FOR I%=L% TO R%-1%
1250 IF B$(I%)>B$(I%+1) T$=B$(I%) : B$(I%)=B$(I%+1%) : B$(I%+1%)=T$ : J%=I%
1260 NEXT I% : R%=J% : J%=0% : FOR I%=R% TO L%+1% STEP -1%
1270 IF B$(I%)<B$(I%-1%) T$=B$(I%) : B$(I%)=B$(I%-1%) : B$(I%-1%)=T$ : J%=I%
1280 NEXT I% : IF J% THEN 1240 ELSE RETURN
1300 REM
1310 REM Selection sort KNUTH 5.2.3 S
1320 REM
1330 FOR I%=1% TO N%-1% : K%=I% : T$=B$(I%)
1340 FOR J%=I%+1% TO N% : IF T$>B$(J%) T$=B$(J%) : K%=J%
1350 NEXT J% : B$(K%)=B$(I%) : B$(I%)=T$ : NEXT I%
1360 RETURN
1400 REM
1410 REM Selection sort - delayed.
1420 REM
1430 FOR I%=1% TO N%-1% : K%=I%
1440 FOR J%=I%+1% TO N% : IF B$(K%)>B$(J%) K%=J%
1450 NEXT J% : IF K%<>I% T$=B$(K%) : B$(K%)=B$(I%) : B$(I%)=T$
1460 NEXT I% : RETURN
1500 REM
1510 REM Insertion sort KNUTH 5.2.1 S
1520 REM
1530 FOR I%=2% TO N% : T$=B$(I%)
1540 FOR J%=I%-1% TO 1% STEP -1% : IF T$<B$(J%) B$(J%+1%)=B$(J%) : NEXT J%
1550 B$(J%+1%)=T$ : NEXT I% : RETURN
1600 REM
1610 REM Batcher's sort  jfr KNUTH 5.2.2 M
1620 REM
1630 H%=-INT(-LOG(N%)/LOG(2%)) : P%=2%^H% : Q1%=P%/2%
1640 FOR T%=1% TO H% : P1%=P% : P%=P%/2% : Q%=Q1% : R%=0% : D%=P%
1650 FOR J%=R% TO N%-D%-1% STEP P1% : K%=J%+P% : IF K%>N%-D% K%=N%-D%
1660 FOR I%=J%+1% TO K% : IF B$(I%)>B$(I%+D%) T$=B$(I%) : B$(I%)=B$(I%+D%) : B$(I%+D%)=T$
1670 NEXT I% : NEXT J% : IF Q%>P% D%=Q%-P% : Q%=Q%/2% : R%=P% : GOTO 1650
1680 NEXT T% : RETURN
1700 REM
1710 REM Shell's sort KNUTH 5.2.1 D (variant)
1720 REM
1730 H%=N%
1740 H%=H%/2% : IF H%=0% RETURN
1750 FOR J%=H%+1% TO N% : T$=B$(J%)
1760 FOR I%=J%-H% TO 1% STEP -H% : IF T$<B$(I%) B$(I%+H%)=B$(I%) : NEXT I%
1770 B$(I%+H%)=T$ : NEXT J% : GOTO 1740
1800 REM
1810 REM Shell's sort KNUTH 5.2.1 D
1820 REM
1821 REM Originalets WHILE/WEND utbytta mot IF/THEN
1822 REM
1830 H%=13%
1835 IF H%<N% H%=3%*H%+1% : GOTO 1835 ELSE H%=(H%-4%)/9%
1840 FOR J%=H%+1% TO N% : T$=B$(J%)
1850 FOR I%=J%-H% TO 1% STEP -H% : IF T$<B$(I%) B$(I%+H%)=B$(I%) : NEXT I%
1860 B$(I%+H%)=T$ : NEXT J% : H%=(H%-1%)/3% : IF H%=0% RETURN ELSE 1840
1900 REM
1904 REM Quick sort KNUTH 5.2.2 Q
1908 REM
1912 REM
1916 R%=N% : L%=1% : M%=10% : REM [ndras f|r annat M eller delsortering
1920 REM Avsteg fr}n originalet IF K<1... ty om DIM L(-n) dyker datorn
1924 K%=LOG((N%+1%)/(M%+2%))/LOG(2%) : IF K%<1% K%=1
1926 DIM L%(K%),R%(K%) : REM Max stack
1928 REM
1932 IF R%-L%>M% K%=0% ELSE 1988
1936 I%=L%+1% : J%=(L%+R%)/2% : T$=B$(J%) : B$(J%)=B$(I%) : B$(I%)=T$ : J%=R%
1940 IF B$(L%)>B$(I%) T$=B$(L%) : B$(L%)=B$(I%) : B$(I%)=T$
1944 IF B$(I%)>B$(R%) T$=B$(R%) : B$(R%)=B$(I%) : B$(I%)=T$
1948 IF B$(L%)>B$(I%) T$=B$(L%) : B$(L%)=B$(I%) : B$(I%)=T$
1952 I%=I%+1% : IF T$>B$(I%) GOTO 1952
1956 J%=J%-1% : IF T$<B$(J%) GOTO 1956
1960 IF J%>I% A$=B$(I%) : B$(I%)=B$(J%) : B$(J%)=A$ : GOTO 1952
1964 B$(L%+1%)=B$(J%) : B$(J%)=T$ : H%=R%-J% : I%=J%-L%
1968 IF H%>=I% AND I%>M% K%=K%+1% : L%(K%)=J%+1% : R%(K%)=R% : R%=J%-1% : GOTO 1936
1972 IF I%>H% AND H%>M% K%=K%+1% : L%(K%)=L% : R%(K%)=J%-1% : L%=J%+1% : GOTO 1936
1976 IF I%>M% AND H%<=M% R%=J%-1% : GOTO 1936
1980 IF H%>M% AND I%<=M% L%=J%+1% : GOTO 1936
1984 IF K% L%=L%(K%) : R%=R%(K%) : K%=K%-1% : GOTO 1936
1988 GOTO 1530
2000 REM
2005 REM Heap sort KNUTH 5.2.3 H
2010 REM
2015 R%=N% : L%=R%/2%+1%
2020 IF L%>1% L%=L%-1% : T$=B$(L%) : GOTO 2030
2025 T$=B$(R%) : B$(R%)=B$(1%) : R%=R%-1% : IF R%=1% B$(1%)=T$ : RETURN
2030 J%=L%
2035 I%=J% : J%=J%+J% : IF J%>R% GOTO 2050
2040 IF J%<R% IF B$(J%)<B$(J%+1%) J%=J%+1%
2045 B$(I%)=B$(J%) : GOTO 2035
2050 J%=I% : I%=J%/2% : IF J%<>L% IF T$>B$(I%) B$(J%)=B$(I%) : GOTO 2050
2055 B$(J%)=T$ : GOTO 2020