qsort.src

;  qsort - 6502 implementation of iterative quicksort algorithm
;
;  Copyright (C) 2004 Matthias Reichl <hias@horus.com>
;
;  This program is free software; you can redistribute it and/or modify
;  it under the terms of the GNU General Public License as published by
;  the Free Software Foundation; either version 2 of the License, or
;  (at your option) any later version.
;
;  This program is distributed in the hope that it will be useful,
;  but WITHOUT ANY WARRANTY; without even the implied warranty of
;  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;  GNU General Public License for more details.
;
;  You should have received a copy of the GNU General Public License
;  along with this program; if not, write to the Free Software
;  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

;  usage:
;  call QSORT with the following parameters:
;  A  =  number of elements (1..255)
;  X  =  lo-address of compare routine
;  Y  =  hi-address of compare routine
;
;  the compare routine should compare the two elements
;  with indices X and Y and must return
;  $FF if element(X) < element(Y)
;  $00 if element(X) = element(Y)
;  $01 if element(X) > element(Y)
;
;  when QSORT returns, the QINDEX table contains the indices of
;  the sorted elements at position 0..len-1

	.LOCAL

?MAXSTK	= 8

QSORT	STX ?COMP+1
	STY ?COMP+2
	CMP #0
	BNE ?HASELE
?NOSORT	RTS

; init index table

?HASELE	STA ?LEN1
	LDX #0
?INIIDX	TXA
	STA QINDEX,X
	INX
	CPX ?LEN1
	BNE ?INIIDX

	LDA ?LEN1
	CMP #1
	BEQ ?NOSORT
	SEC
	SBC #1
	STA ?RSTACK
	STA ?RIGHT
	LDA #0
	STA ?LSTACK
	STA ?STACKP
	STA ?LEFT

; main quicksort loop

?LOOP	LDA ?LEFT
	STA ?I
	LDA ?RIGHT
	STA ?J
	STA ?KEY

; start of partitioning loop

?PART1	LDA ?I
	CMP ?J
	BCS ?PART2

	TAX
	LDY ?KEY
	JSR ?COMPAR
	CMP #1
	BEQ ?PART2
	INC ?I
	BNE ?PART1

?PART2	LDA ?I
	CMP ?J
	BCS ?PARTE

	LDX ?KEY
	LDY ?J
	JSR ?COMPAR
	CMP #1
	BEQ ?PARTE
	DEC ?J
	BNE ?PART2

?PARTE	LDA ?I
	CMP ?J
	BCS ?NSWAP1
	LDX ?I
	LDY ?J
	LDA QINDEX,X
	PHA
	LDA QINDEX,Y
	STA QINDEX,X
	PLA
	STA QINDEX,Y

?NSWAP1	LDA ?I
	CMP ?J
	BCC ?PART1

	LDX ?I
	LDY ?RIGHT
	LDA QINDEX,X
	PHA
	LDA QINDEX,Y
	STA QINDEX,X
	PLA
	STA QINDEX,Y

; end of partitioning loop

	SEC
	LDA ?I
	SBC ?LEFT
	STA ?LEN1

	SEC
	LDA ?RIGHT
	SBC ?I
	STA ?LEN2

	LDA ?LEN1
	CMP ?LEN2
	BCC ?PUSHR

	LDA ?LEFT
	CMP ?I
	BEQ ?NOPSHL

	INC ?STACKP
	LDX ?STACKP
;	CPX #?MAXSTK
;	BNE ?STOK1
;	JMP QERROR
?STOK1	STA ?LSTACK,X
	SEC
	LDA ?I
	SBC #1
	STA ?RSTACK,X

?NOPSHL	LDA ?I
	CMP ?RIGHT
	BEQ ?DOPOP

	CLC
	LDA ?I
	ADC #1
	STA ?LEFT
	JMP ?NEXT

?PUSHR	LDA ?I
	CMP ?RIGHT
	BEQ ?NOPSHR

	INC ?STACKP
	LDX ?STACKP
;	CPX #?MAXSTK
;	BNE ?STOK2
;	JMP QERROR
?STOK2	CLC
	LDA ?I
	ADC #1
	STA ?LSTACK,X
	LDA ?RIGHT
	STA ?RSTACK,X

?NOPSHR	LDA ?I
	CMP ?LEFT
	BEQ ?DOPOP

	SEC
	SBC #1
	STA ?RIGHT
	JMP ?NEXT

?DOPOP	LDX ?STACKP
	DEC ?STACKP
	LDA ?LSTACK,X
	STA ?LEFT
	LDA ?RSTACK,X
	STA ?RIGHT

?NEXT	LDA ?STACKP
	CMP #$FF
	BEQ ?END
	JMP ?LOOP

?COMPAR	LDA QINDEX,X
	TAX
	LDA QINDEX,Y
	TAY
?COMP	JMP 12345

?END	RTS

?LSTACK	.DC ?MAXSTK 0
?RSTACK	.DC ?MAXSTK 0
?STACKP	.BYTE 0

?LEFT	.BYTE 0
?RIGHT	.BYTE 0
?I	.BYTE 0
?J	.BYTE 0
?KEY	.BYTE 0
?LEN1	.BYTE 0
?LEN2	.BYTE 0

QINDEX	.DC 256 0