10 ;--------------- QUICKSORT.ASS ---------------
11 ;
900 ; ------------------------ VARIABLEN IN DER ZERO PAGE
901 ;
902 .BA   50 000   ; START ADRESSE
903 .EQ XADR=10    ; ADR.  A$(X) IN (10,11)
904 .EQ YADR=12    ; ADR.  A$(Y) IN (12,13)
905 .EQ VADR=14    ; ADR.  A$(V) IN (14,15)
906 .EQ XDES=16    ; DESCR. A$(X) IN (16,17,18)
907 .EQ YDES=19    ; DESCR. A$(Y) IN (19,20,21)
908 .EQ VDES=22    ; DESCR. A$(V) IN (22,23,24)
909 .EQ LG = 25    ; LINKE GRENZE IN (25,26)
910 .EQ RG = 27    ; RECHTE GRENZE IN (27,28)
911 .EQ VERL=29    ; VERGLEICHS LAENGEREADY.
912 .EQ STIN=252   ; STACK EINGANGSWERT
913 .EQ STMI=253   ; STACK MINIMUM
914 .EQ STUG=254   ; STACK UNTERGRENZE
915 ;
1000 ; ------------------------ BASIC-DATEN RETTEN
1100 ;STACK-POINTER ------
1110  TSX
1120  STXSTIN
1125  STXSTMI
1130  TXA; STACK -
1140  SEC; UNTERGRENZE
1150  SBC#82; BERECHNEN
1160  BCSSPR
1170  RTS; ABBRUCH
1180 SPR ADC#2; 3 BYTE
1190  STASTUG; UEBER 0
1195 ;
1200 ;ZERO-PAGE ---------
1210  LDX#19
1220 ZPWEG LDA10,X
1230  PHA
1240  DEX
1250  BPLZPWEG
1260  TSX
1270  STXSTIN
2000 ; ------------------------ ANFANGS - BEDINGUNGEN
2100 ; Z = 0 ----------
2110 SORT LDA#0
2120  PHA
2130  PHA
2200 ; LG = 1 ----------
2210  CLC
2220  LDA47; FELDANFANG
2230  ADC#10; IN (47,48)
2240  STALG;  + 10 BYTE
2250  LDA48;  VORSPANN
2260  ADC#0;  ERGIBT
2270  STALG+1; ADR A$(1)
2300 ; RG = A ----------
2310  CLC; FELDLAENGE
2320  LDY#2; STEHT  IM
2330  LDA(47),Y; VORSPANN
2340  ADC47;   PLUS
2350  TAX; FELDANFANG
2360  INY
2370  LDA(47),Y
2380  ADC48
2390  TAY
2400  SEC
2410  TXA;   MINUS
2420  SBC#3;   3 BYTE
2430  STARG; FUER LETZTEN
2440  PHA; DESCRIPTOR
2450  TYA;  ERGIBT
2460  SBC#0; ADR A$(A)
2470  STARG+1
2480  PHA
2490  BNEVSTRING
2500 ; Z = 1 ----------
2510 ;         BEDEUTET RG(1) AUF STACK LEGEN
2520 ;         SIEHE ZEILE 2440 UND 2480
2530 BRUECKE4 BNESORT
2540 ;
3000 ;------------------------ VERGLEICHSSTRING BERECHNEN
3100 ;X=LG:Y=RG ----------
3110 VSTRING LDX#3
3120 LADXY LDALG,X
3130  STAXADR,X;   LADE -
3140  DEX;  SCHLEIFE
3150  BPLLADXY
3200 ;V = X + Y ----------
3210  CLC
3220  LDAXADR
3230  ADCYADR
3240  TAX
3250  LDAXADR+1
3260  ADCYADR+1
3300 ;V = INT(V/2) ----------
3310  LSR; HIGH BYTE
3320  STAVADR+1; RECHTS SHIFT
3330  TXA; LOW BYTE
3340  ROR; ROTATION
3350  BCCSPR1; RECHTS
3360  SBC#1; INT -
3370  BCSSPR1; MODULO
3380  DECVADR+1;   3
3390 SPR1 STAVADR
3400 ;V$ = A$(V) ----------
3410  LDY#0; DESCRIPTOR
3420  LDA(VADR),Y;   A$(V)
3430  STAVDES;  IN DER
3440  INY; ZERO PAGE
3450  LDA(VADR),Y; SPEICHERN
3460  STAVDES+1
3470  INY
3480  LDA(VADR),Y
3490  STAVDES+2
3495 ;
4000 ; ------------------------ X - VERGLEICHSSCHLEIFE
4100 ;X$ = A$(X) ----------
4110 VERGLX LDY#0; DESCRIPTOR
4120  LDA(XADR),Y;   A$(X)
4130  STAXDES;  IN DER
4140  INY; ZERO PAGE
4150  LDA(XADR),Y; SPEICHERN
4160  STAXDES+1
4170  INY
4180  LDA(XADR),Y
4190  STAXDES+2
4200 ;VERGLEICHS-LAENGE ----------
4210  LDX#0; X$ KUERZER:
4220  LDAXDES;  XREG=0
4230  CMPVDES;  VERL=LEN(X$)
4240  BCCSPR2; V$ KUERZER:
4250  INX;  XREG=1
4260  LDAVDES;  VERL=LEN(V$)
4270 SPR2 STAVERL
4300 ;X$ <?> V$ ----------
4310  LDY#0; HAUPTSCHLEIFE
4320 VERGLX1 LDA(XDES+1),Y; -------------
4330  CMP(VDES+1),Y; BYTE UM BYTE
4340  BNEVERGLX2; VERGLEICHEN
4350  INY
4360  CPYVERL; VERGL.LAENGE
4370  BCCVERGLX1;   PRUEFEN
4380  CPX#1
4390 VERGLX2 BCSVERGLY
4400 ;X = X + 1 ----------
4410  CLC
4420  LDAXADR; LOW-BYTE
4430  ADC#3;   + 3
4440  STAXADR; ZEIGT AUF
4450  BCCVERGLX; NAECHSTEN
4460  INCXADR+1; DESCRIPTOR
4470  BCSVERGLX
4480 ;SPRUNG --------------
4490 BRUECKE1 BCCVSTRING
4491 BRUECKE5 BNEBRUECKE4
4495 ;
5000 ; ------------------------ Y - VERGLEICHSSCHLEIFE
5100 ;Y$ = A$(Y) ----------
5110 VERGLY LDY#0; DESCRIPTOR
5120  LDA(YADR),Y;   A$(Y)
5130  STAYDES;  IN DER
5140  INY; ZERO PAGE
5150  LDA(YADR),Y; SPEICHERN
5160  STAYDES+1
5170  INY
5180  LDA(YADR),Y
5190  STAYDES+2
5200 ;VERGLEICHS-LAENGE ----------
5210  LDX#0; V$ KUERZER:
5220  LDAVDES;  XREG=0
5230  CMPYDES;  VERL=LEN(V$)
5240  BCCSPR3; Y$ KUERZER :
5250  INX;  XREG=1
5260  LDAYDES;  VERL=LEN(Y$)
5270 SPR3 STAVERL
5300 ;Y$ <?> V$ ----------
5310  LDY#0; HAUPTSCHLEIFE
5320 VERGLY1 LDA(VDES+1),Y; -------------
5330  CMP(YDES+1),Y; BYTE UM BYTE
5340  BNEVERGLY2; VERGLEICHEN
5350  INY
5360  CPYVERL; VERGL.LAENGE
5370  BCCVERGLY1;   PRUEFEN
5380  CPX#1
5390 VERGLY2 BCSTAUSCH
5400 ;Y = Y - 1 ----------
5410  SEC
5420  LDAYADR; LOW-BYTE
5430  SBC#3;   - 3
5440  STAYADR; ZEIGT AUF
5450  BCSVERGLY; VORHERIGEN
5460  DECYADR+1; DESCRIPTOR
5470  BCCVERGLY
5480 ;SPRUNG --------------
5490 BRUECKE2 BCSVERGLX
5491 BRUECKE3 BCCBRUECKE1
5492 BRUECKE6 BNEBRUECKE5
5495 ;
6000 ; ------------------------ STRINGS VERTAUSCHEN
6100 ;IF X>=Y  ----------
6110 TAUSCH LDAYADR+1; HIGH
6120  CMPXADR+1; BYTES
6130  BCCZSTUFEN; X>Y
6140  BNESWAP; X<Y
6150  LDAXADR; LOW
6160  CMPYADR; BYTES
6170  BCSZSTUFEN; X>=Y
6200 ;SWAP X$,Y$ ----------
6210 SWAP LDX#2
6220  LDY#2
6230 SWAP1 LDAXDES,X; X-DESCRIPTOR
6240  STA(YADR),Y;  NACH A$(Y)
6250  LDAYDES,X; Y-DESCRIPTOR
6260  STA(XADR),Y;  NACH A$(X)
6270  DEX
6280  DEY
6290  BPLSWAP1
6300 ;X = X + 1 ----------
6310  CLC
6320  LDAXADR; SIEHE
6330  ADC#3; ZEILE
6340  STAXADR; 4400
6350  BCCSPR4
6360  INCXADR+1
6400 ;Y = Y - 1 ----------
6410 SPR4 SEC
6420  LDAYADR; SIEHE
6430  SBC#3; ZEILE
6440  STAYADR; 5400
6450  BCSSPR5
6460  DECYADR+1
6500 ;IF X <= Y ----------
6510 SPR5 LDAYADR+1
6520  CMPXADR+1
6530  BCCZSTUFEN; X>Y
6540  BNEBRUECKE2; X<Y
6550  LDAYADR
6560  CMPXADR
6570  BCSBRUECKE2; X<=Y
6580  BCCZSTUFEN; X>Y
6600 ; SPRUNG --------------
6610 BRUECKE7 BNEBRUECKE6
7000 ;------------------------ STUFEN-VERZWEIGUNG
7100 ;Z=Z+1:RG=Y ----------
7110 ZPLUS LDARG; Z = Z + 1
7120  PHA; BEDEUTET
7130  LDARG+1; RG AUF STACK
7140  PHA; LEGEN
7150  LDAYADR
7160  STARG;   RG
7170  LDAYADR+1;    =
7180  STARG+1;    Y
7185  CLC; NEUEN V$
7190  BCCBRUECKE3;BERECHNEN
7200 ;LG = LG + 1 ----------
7210 ZGLEICH CLC
7220  LDALG
7230  ADC#3; SIEHE
7240  STALG; ZEILE
7250  BCCSPR6; 4400
7260  INY
7270 SPR6 STYLG+1
7300 ;IF LG < RG ----------
7310  CPYRG+1
7320  BCCBRUECKE3; LG<RG
7330  BNEZMINUS; LG>RG
7340  CMPRG
7350  BCCBRUECKE3; LG<RG
7360  BCSZMINUS; LG>=RG
7400 ;IF LG < RG ----------
7410 ZSTUFEN LDALG
7420  LDYLG+1
7430  CPYYADR+1
7440  BCCSTACK; LG<RG
7450  BNEZGLEICH; LG>RG
7460  CMPYADR
7470  BCCSTACK; LG<RG
7480  BCSZGLEICH; LG>=RG
7500 ;STACK PRUEFEN -------
7510 STACK TSX
7520  CPXSTMI; STACKMINIMUM
7530  BCSZPLUS; PRUEFEN
7540  STXSTMI
7550  CPXSTUG; STACK-UG
7560  BCSZPLUS; PRUEFEN
7570  LDXSTIN; RUECKSPRUNG
7580  TXS; ZUM
7585  BNEBRUECKE7; ANFANG
7600 ;Z = Z - 1 ----------
7610 ZMINUS PLA; Z = Z - 1
7620  STARG+1; BEDEUTET
7630  PLA; RG VOM STACK
7640  STARG; HOLEN
7650  LDXRG+1
7660  CPX#0; RG HIGHBYTE
7670  BNEZGLEICH;    > 0
7680 ;                        ;    = 0
8000 ; ----------------------- BASIC-DATEN SPEICHERN
8100 ;STACK-POINTER -----
8110 AUS LDXSTIN
8120  TXS
8200 ;ZERO-PAGE ---------
8210  LDX#0
8220 ZPRUECK PLA
8230  STA10,X
8240  INX
8250  CPX#20
8260  BCCZPRUECK
8270  RTS