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

; File : SHAKE.MAC

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

	ext	curline,cmpidx,swap
	ext	ptr.1,ptr.2,ptr.3,ptr.4

	entry	SHAKE

; Sortieren der Elemente
; Routine fuehrt den Shake Sort Algorithmus aus
; basierend auf einem Artikel in MC 1'81
;
SHAKE:
	ld	hl,2		; Zeiger setzen
	ld	(ptr.1),hl
	ld	hl,(curline)
	ld	(ptr.2),hl
	dec	hl
	ld	(ptr.3),hl
repeat:
	ld	hl,(ptr.2)
	ld	(ptr.4),hl	; Schleife 1 setzen
	jr	..nxt.1
next.1:
	call	..loop		; Austausch wenn noetig
	ld	hl,(ptr.4)
	dec	hl
	ld	(ptr.4),hl
..nxt.1:
	ld	de,(ptr.1)
	or	a
	sbc	hl,de
	jr	nc,next.1
	ld	hl,(ptr.3)
	inc	hl		; Zeiger holen
	ld	(ptr.1),hl
	ld	(ptr.4),hl
	jr	..nxt.2
next.2:
	call	..loop		; .. vielleicht austauschen
	ld	hl,(ptr.4)
	inc	hl
	ld	(ptr.4),hl
..nxt.2:
	ld	de,(ptr.2)
	inc	de
	or	a
	sbc	hl,de
	jr	c,next.2	; Schleife testen
	ld	hl,(ptr.3)
	dec	hl
	ld	(ptr.2),hl	; Naechster Versuch
	ld	de,(ptr.1)
	or	a
	sbc	hl,de		; Test ob alles fertig
	jr	nc,repeat
	ret
;
; Austausch zweier aufeinanderfolgender Elemente
;
..loop:
	ld	hl,(ptr.4)	; Zeiger holen
	push	hl
	dec	hl
	push	hl
	call	cmpidx		; Vergleich
	pop	de
	pop	hl
	ret	nc		; .. kein Austausch
	ld	(ptr.3),hl	; Zeiger retten
	call	swap		; Austausch
	ret

	end