1 REM Ins{nd av Olle Nilsson <975>    1985-08-22 12.48.39
100 ! 
110 ! FNSORT  .MRG    Ver. 1.20  850821
120 ! 
130 ! (C) Olle Nilsson, DATEC, Uppsala
140 ! 
150 ! Usage: F}r brukas privat av ABC-Klubbens medlemmar (i okommersiella 
160 ! .      syften!)
170 ! 
180 ! F|rdelar med f|ljande rutiner:
190 ! 
200 ! a) Definierbar sorteringsrutin, {ndra bara ordningen i Order$!
210 ! b) Bin{rs|kning anv{nds! (snabbheten m{rks f|rst vid stora datam{ngder)
220 ! 
230 ! The smart programmer strikes again!
240 ! *             >TSP<               *
250 ! 
260 ! ------------------------------------------------------------------
270 ! 
280 ! F|r att snabba upp rutinerna kan man:
290 ! 
300 ! 1) [ndra WHILE/WEND till FOR/NEXT
310 ! 2) Skippa FNBigchar$ (l{ser sm} tecken som stora vid test)
320 ! 3) Ta bort REM-satser i loopar
330 ! 4) Skriva FNCompare%(S1$,S2$), FNBigchar$(S$) och FNInsert%(Pos%,Top%)
340 ! .  i maskinkod (sparar *MYCKET* tid!)
350 ! 
360 ! Det f|ruts{tts att inga str{ngar inneh}ller tecken med ASCII<32 eller
370 ! ASCII>127! (Dessa tecken hamnar annars f|re 'A' i listan! Men man kan
380 ! ju om man vill l{gga in dylika tecken i Order$.)
390 ! 
400 ! Funktionen anropas med Z%=FNSort%(Maxindex%)
410 ! 
420 ! ------------------------------------------------------------------
430 EXTEND : FLOAT : OPTION BASE 1%
440 DIM Namn$(200%)=30% ! Dimesionering av sorteringsvektor
450 ! ------------------------------------------------------------------
460 Order$='ABCDE@FGHIJKLMNOPQRSTUVWXYZ][\^ 0123456789.,!?:;-+*/=><()#$&%_"'''+CHR$(127%)
470 ! ------------------------------------------------------------------
480 DEF FNCompare%(S1$,S2$) LOCAL K%,L%,L1%,L2%,I1%,I2%,M1$=1,M2$=1
490   L1%=LEN(S1$) : L2%=LEN(S2$) : IF L1%>L2% L%=L2% ELSE L%=L1%
500   K%=1% : WHILE K%<=L%
510     M1$=FNBigchar$(MID$(S1$,K%,1%)) : M2$=FNBigchar$(MID$(S2$,K%,1%))
520     I1%=INSTR(1%,Order$,M1$) : I2%=INSTR(1%,Order$,M2$)
530     IF I1%<I2% RETURN -1% ! S1$ f|re S2$
540     IF I1%>I2% RETURN 1% ! S2$ f|re S1$
550   K%=K%+1% : WEND 
560   IF L1%<L2% RETURN -1%
570   RETURN 0% ! Identiska str{ngar
580 FNEND 
590 DEF FNBigchar$(S$)
600   IF (S$<'`' OR S$>'~') RETURN S$
610   RETURN CHR$(ASCII(S$) AND 223%)
620 FNEND 
630 DEF FNInsert%(Pos%,Top%) LOCAL K%
640   ! Top% = Position som ska flyttas ned
650   ! Pos% = Position d{r ins{ttning ska ske
660   Namn$=Namn$(Top%)
670   K%=Top%-1% : WHILE K%>=Pos%
680     Namn$(K%+1%)=Namn$(K%)
690   K%=K%-1% : WEND 
700   Namn$(Pos%)=Namn$
710   RETURN 0%
720 FNEND 
730 ! ------------------------------------------------------------------
740 ! Sortering (Maxno% = h|gsta vektorindex som ska sorteras)
750 ! 
760 DEF FNSort%(Maxno%) LOCAL Bottom%,C%,I%,Last%,No%,Top%
770   IF Maxno%<2% RETURN 0% ! No sort
780   I%=2% : WHILE I%<=Maxno%
790     IF FNCompare%(Namn$(I%),Namn$(I%-1%))>-1% GOTO 920 ! No sort needed
800     ! Bin{rs|kning
810     Bottom%=1% : Top%=I% : Last%=0%
820     No%=(Bottom%+Top%)/2%
830     IF Last%=No% 900 ! Not Found
840     C%=FNCompare%(Namn$(I%),Namn$(No%))
850     IF C%=-1% Top%=No% ! Lower section
860     IF C%=1% Bottom%=No% ! Upper section
870     IF C%=0% 910 ! Found
880     Last%=No%
890     GOTO 820
900     IF C%=-1% No%=No%-1%
910     Z%=FNInsert%(No%+1%,I%)
920   I%=I%+1% : WEND : RETURN 0%
930 FNEND 
940 ! ------------------------------------------------------------------