title	Routine zum QUICK SORT fuer CP/M
	name	('QUICK')
	maclib	base80

; File : QUICK.MAC

; ===== Externe Referenzen ====

	ext	curline,ass1,cmpxdm,@swap
	ext	ptr.1,ptr.2,ptr.3,ptr.4

	entry	QUICK

_STKDP	equ	30

; Sortieren der Elemente
; Routine fuehrt den Quick Sort Algorithmus aus
; basierend auf einem Artikel in MC 1'81
;
QUICK:
	ld	ix,s.1-2	; Stack laden
	ld	iy,s.2-2
	ld	hl,0
	ld	(s1),hl
	inc	hl
	ld	de,(curline)
	call	.push		; Werte ablegen
quick.1:
	call	.pop		; Werte holen
	ld	(ptr.1),hl
	ld	(ptr.2),de
quick.2:
	ld	hl,(ptr.2)
	ld	(ptr.4),hl
	ld	hl,(ptr.1)
	ld	(ptr.3),hl
	add	hl,de
	srl	h		; Zeiger holen
	rr	l
	call	ass1		; Element laden
quick.3:
	ld	hl,(ptr.3)
.quick.3:
	push	hl
	call	cmpxdm		; Elemente vergleichen
	pop	hl
	jr	nc,quick.4
	ld	de,(ptr.2)
	or	a
	sbc	hl,de		; Zeiger vergleichen
	jr	nc,quick.4
	add	hl,de
	inc	hl		; Zeiger + 1
	ld	(ptr.3),hl
	jr	.quick.3
quick.4:
	ld	hl,(ptr.4)
.quick.4:
	push	hl
	call	cmpxdm		; Elemente vergleichen
	pop	hl
	jr	c,quick.5
	jr	z,quick.5
	ld	de,(ptr.1)
	inc	de
	or	a
	sbc	hl,de		; Zeiger vergleichen
	jr	c,quick.5
	add	hl,de
	dec	hl		; Zeiger + 1
	ld	(ptr.4),hl
	jr	.quick.4
quick.5:
	ld	hl,(ptr.3)	; Test ob Austausch
	push	hl
	ld	de,(ptr.4)
	push	de
	inc	de
	or	a
	sbc	hl,de
	pop	de
	pop	hl
	jr	nc,quick.6
	push	hl
	push	de
	call	@swap		; Austausch
	pop	hl
	dec	hl
	ld	(ptr.4),hl	; Neuen Zeiger speichern
	pop	hl
	inc	hl
	ld	(ptr.3),hl
quick.6:
	ld	hl,(ptr.3)	; Test ob Austausch
	push	hl
	ld	de,(ptr.4)
	push	de
	inc	de
	or	a
	sbc	hl,de
	pop	hl
	pop	bc
	jr	c,quick.3
	ld	de,(ptr.1)
	or	a
	sbc	hl,de
	ex	de,hl
	inc	de
	ld	hl,(ptr.2)
	or	a
	sbc	hl,bc
	or	a
	sbc	hl,de
	jr	c,quick.8
	ld	hl,(ptr.1)
	push	hl
	ld	de,(ptr.4)
	or	a
	sbc	hl,de
	pop	hl
	jr	nc,quick.7
	call	.push
quick.7:
	ld	hl,(ptr.3)
	ld	(ptr.1),hl
	jr	quick.10
quick.8:
	ld	hl,(ptr.3)
	push	hl
	ld	de,(ptr.2)
	or	a
	sbc	hl,de
	pop	hl
	jr	nc,quick.9
	call	.push
quick.9:
	ld	hl,(ptr.4)
	ld	(ptr.2),hl
quick.10:
	ld	hl,(ptr.2)	; Test inneren Durchlauf
	ld	de,(ptr.1)
	inc	de
	or	a
	sbc	hl,de
	jp	nc,quick.2
	ld	hl,(s1)		; Test ob Rest
	ld	a,l
	or	h
	jp	nz,quick.1
	ret
;
; Daten auf dem Stack ablegen
;
.push:
	ld	bc,2
	add	ix,bc		; Stack fixieren
	add	iy,bc
	ld	(ix+0),l	; Daten ablegen
	ld	(ix+1),h
	ld	(iy+0),e
	ld	(iy+1),d
	ld	hl,(s1)
	inc	hl
	ld	(s1),hl
	ret
;
; Daten vom Stack holen
;
.pop:
	ld	hl,(s1)
	dec	hl
	ld	(s1),hl
	ld	l,(ix+0)	; Daten holen
	ld	h,(ix+1)
	ld	e,(iy+0)
	ld	d,(iy+1)
	ld	bc,-2
	add	ix,bc		; Stack fixieren
	add	iy,bc
	ret

	dseg

;
; Stack fuer Zwischenablage
;
s1:
	ds	2
s.1:
	ds	_STKDP*2
s.2:
	ds	_STKDP*2

	end