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

; File : HEAP.MAC

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

	ext	curline,swap,ass1,ass2,ass4,cmpidx,cmpxdm
	ext	ptr.1,ptr.2,ptr.3,ptr.4

	entry	HEAP

; Sortieren der Elemente
; Routine fuehrt den Heap Sort Algorithmus aus
; basierend auf einem Artikel in MC 1'81
;
HEAP:
	ld	hl,(curline)	; Maximalwert holen
	ld	(ptr.2),hl
	srl	h		; Durch zwei dividieren
	rr	l
	inc	hl		; .. justieren
	ld	(ptr.1),hl
sort.1:
	ld	hl,(ptr.1)
	ld	de,1+1
	or	a
	sbc	hl,de		; Test Zeiger > 1
	jr	nc,sort.2
	ld	hl,(ptr.2)
	ld	de,1+1
	or	a
	sbc	hl,de		; Test Zeiger <= 1
	jr	c,sort.3
	ld	hl,(ptr.1)
	ld	de,(ptr.2)
	call	swap		; Elemente austauschen
	ld	hl,(ptr.2)
	dec	hl		; Zeiger fixieren
	ld	(ptr.2),hl
	jr	sort.3
sort.2:
	ld	hl,(ptr.1)
	dec	hl
	ld	(ptr.1),hl
sort.3:
	ld	hl,(ptr.1)
	ld	(ptr.3),hl
	push	hl
	add	hl,hl
	ld	(ptr.4),hl
	pop	hl
	call	ass1		; Element speichern
	ld	hl,(ptr.2)
	ld	de,(ptr.4)
	or	a
	sbc	hl,de		; Zeiger testen
	jr	c,sort.6
sort.4:
	ld	hl,(ptr.4)
	ld	de,(ptr.2)
	or	a
	sbc	hl,de		; Zeiger testen
	jr	nc,sort.5
	ld	hl,(ptr.4)
	call	cmpidx		; Elemente vergleichen
	jr	c,sort.5
	jr	z,sort.5
	ld	hl,(ptr.4)
	inc	hl
	ld	(ptr.4),hl
sort.5:
	ld	hl,(ptr.2)
	ld	de,(ptr.4)
	or	a
	sbc	hl,de		; Zeiger testen
	jr	c,sort.6
	ld	hl,(ptr.4)
	call	cmpxdm		; Elemente vergleichen
	jr	c,sort.6
	jr	z,sort.6
	ld	hl,(ptr.3)
	ld	de,(ptr.4)
	call	ass4
	ld	hl,(ptr.4)
	ld	(ptr.3),hl
	add	hl,hl
	ld	(ptr.4),hl
	jr	sort.4
sort.6:
	ld	hl,(ptr.3)
	call	ass2
	ld	hl,(ptr.2)
	ld	de,1
	or	a
	sbc	hl,de		; Test ob alles fertig
	jp	nz,sort.1
	ret

	end