6809_QSORT.s

	.macro	CLC
		ANDCC	#$FE
	.endm

	.macro	SEC
		ORCC	#$01
	.endm

;	Title:			Quicksort
;	Name:			QSORT
;
;	Purpose:		Arrange an array of unsigned words into ascending order
;				using a quicksort, with a maximum size of 32767 words.
;
;	Entry:
;				TOP OF STACK
;	
;				High byte of return address
;				Low  byte of return address
;				High byte of address of first word in array 
;				Low  byte of address of first word in array 
;				High byte of address of last word in array 
;				Low  byte of address of last word in array 
;				High byte of lowest available stack address 
;				Low  byte of lowest available stack address
;
;	Exit:			If the stack did not overflow then 
;					The array is sorted into ascending order.
;					Carry = 0
;				Else
;					Carry = 1 
;
;	Registers Used:		All
;
;	Time:			The timing is highly data-dependent but the
;				quicksort algorithm takes approximately
;				N * log (N) loops through PARTLP.
;				There will be 2 * N+1 calls to Sort.
;				The number of recursions
;				will probably be a fraction of N but if all
;				data is the same, the recursion could be up to
;				N. Therefore, the amount of stack space should
;				be maximized. 
;				NOTE: Each recursion level takes
;				6 bytes of stack space.
;
;				In the above discussion, 
;				N is the number of array elements.
;	Size:			Program 179 bytes
;				Data 8 bytes plus 4 stack bytes
;
QSORT:

	PULS	D,X,Y,U		; REMOVE PARAMETERS FROM STACK
	PSHS	D		; PUT RETURN ADDRESS BACK IN STACK
				; WATCH FOR STACK OVERFLOW
				; CALCULATE A THRESHOLD TO NARN OF OVERFLOW
				; (10 BYTES FROM THE END OF THE STACK)
				; SAVE THIS THRESHOLD FOR LATER COMPARISONS
				; ALSO SAVE THE POSITION OF THIS ROUTINE'S RETURN ADDRESS
				; IN THE EVENT WE MUST ABORT BECAUSE OF STACK OVERFLOW
	STS	OLDSP		; SAVE POINTER TO RETURN ADDRESS IN
				; CASE WE MUST ABORT
	LEAU	10,U		; ADD SMALL BUFFER (10 BYTES) TO
				; LOWEST STACK ADDRESS
	STU	STKBTM		; SAVE SUM AS BOTTOM OF STACK FOR
				; FIGURING WHEN TO ABORT
				;

; WORK RECURSIVELY THROUGH THE QUICKSORT ALGORITHM AS
; FOLLOWS:
; 1.	CHECK IF THE PARTITION CONTAINS 0 OR 1 ELEMENT.
;	MOVE UP A RECURSION LEVEL IF IT DOES.
; 2.	USE MEDIAN TO OBTAIN A REASONABLE CENTRAL VALUE FOR
;	DIVIDING THE CURRENT PARTITION INTO TWO PARTS.
; 3.	MOVE THROUGH THE ARRAY SWAPPING ELEMENTS THAT ARE OUT OF ORDER
;	UNTIL ALL ELEMENTS BELOW THE CENTRAL VALUE ARE AHEAD OF 
;	ALL ELEMENTS ABOVE THE CENTRAL VALUE.
;	SUBROUTINE COMPARE COMPARES ELEMENTS, SWAP EXCHANGES ELEMENTS, 
;	PREV MOVES UPPER BOUNDARY DOHN ONE ELEMENT, 
;	AND NEXT MOVES LOWER BOUNDARY UP ONE ELEMENT.
; 4.	CHECK IF THE STACK IS ABOUT TO OVERFLOW.
;	IF IT IS, ABORT AND EXIT.
; 5.	ESTABLISH THE BOUNDARIES FOR THE FIRST PARTITION
;	(CONSISTING OF ELEMENTS LESS THAN THE CENTRAL VALUE)
;	AND SORT IT RECURSIVELY.
;	ESTABLISH THE BOUNDARIES FOR THE SECOND PARTITION
;	(CONSISTING OF ELEMENTS GREATER THAN THE CENTRAL VALUE)
;	AND SORT IT RECURSIVELY.
;
SORT:
;
; SAVE BASE ADDRESS AND ADDRESS OF LAST ELEMENT
; IN CURRENT PARTITION
;

PARTLP:	STX	FIRST
	STY	LAST
;
; CHECK IF PARTITION CONTAINS 0 OR 1 ELEMENTS
; IT DOES IF FIRST IS EITHER LARGER THAN (0)
; OR EQUAL YTO (1) LAST.
; STOP WHEN FIRST LAST
;
	CMPX	LAST
	BCC	EXITPR		; SAVE BASE ADDRESS
				; SAVE ADDRESS OF LAST ELEMENT
				; CALCULATE FIRST LAST
				; BRANCH (RETURN) IF DIFFERENCE IS
				; POSITIVE THIS PART IS SORTED
;
; START ANOTHER ITERATION ON THIS PARTITION
; USE MEDIAN TO FIND A REASONABLE CENTRAL ELEMENT
; MOVE CENTRAL ELEMENT TO FIRST POSITION
;
	BSR	MEDIAN		; SELECT CENTRAL ELEMENT, MOVE IT
				; TO FIRST POSITION
	LDU	#0		; BIT 0 OF REGISTER U = DIRECTION
				; IF IT IS 0 THEN DIRECTION IS UP
				; ELSE DIRECTION IS DOWN
;
; REORDER ARRAY BY COMPARING OTHER ELEMENTS WITH THE
; CENTRAL ELEMENT. START BY COMPARING THAT ELEMENT WITH LAST ELEMENT.
; EACH TIME WE FIND AN ELEMENT THAT BELONGS IN THE FIRST PART
; (THAT IS, IT IS LESS THAN THE CENTRAL ELEMENT),
; SWAP IT INTO THE FIRST PART IF IT IS NOT ALREADY THERE
; AND MOVE THE BOUNDARY OF THE FIRST PART DOWN ONE ELEMENT.
; SIMILARLY, EACH TIME WE FIND AN ELEMENT THAT BELONGS IN THE SECOND PART
; (THAT IS, IT IS GREATER THAN THE CENTRAL ELEMENT),
; SWAP IT INTO THE SECOND PART IF IT IS NOT ALREADY THERE
; AND MOVE THE BOUNDARY OF THE SECOND PART UP ONE ELEMENT.
; ULTIMATELY, THE BOUNDARIES COME TOGETHER
; AND THE DIVISION OF THE ARRAY IS THEN COMPLETE
; NOTE THAT ELEMENTS EQUAL TO THE CENTRAL ELEMENT ARE NEVER
; SHAPPED AND SO MAY END UP IN EITHER PART
;
; LOOP SORTING UNEXAMINED PART OF PARTITION
; UNTIL THERE IS NOTHING LEFT IN IT
;
	TFR	X,D		; LOWER BOUNDARY
	PSHS	Y
	CMPD	,S++		; LOWER BOUNDARYUPPER BOUNDARY
	BCC	DONE		; EXIT WHEN EVERYTHING EXAMINED
;
; COMPARE NEXT 2 ELEMENTS. IF OUT OF ORDER, SWAP THEM
; AND CHANGE DIRECTION OF SEARCH
;
; IF FIRST > LAST THEN SWAP
;
	LDD	,X		; COMPARE ELEMENTS
	CMPD	,Y
	BLS	REDPRT		; BRANCH IF ALREADY IN ORDER
;
; ELEMENTS OUT OF ORDER, SWAP THEM AND CHANGE DIRECTION
;
TFR	U,D		; GET DIRECTION
	COMB		; CHANGE DIRECTION
	TFR	D,U	; SAVE NEW DIRECTION
	JSR	SWAP	; SWAP ELEMENTS
;
; REDUCE SIZE OF UNEXAMINED AREA
; IF NEW ELEMENT LESS THAN CENTRAL ELEMENT,
; MOVE TOP BOUNDARY DOWN
; IF NEW ELEMENT GREATER THAN CENTRAL ELEMENT, 
; MOVE BOTTOM BOUNDARY UP
; IF ELEMENTS EQUAL, CONTINUE IN LATEST DIRECTION
;

REDPRT:
	CMPU	#0		; CHECK DIRECTION
	BEQ	UP		; BRANCH IF MOVING UP
	LEAX	2,X		; ELSE MOVE TOP BOUNDARY DOWN BY
				; ONE ELEMENT
	BRA	PARTLP
UP:
	LEAY	-2,Y		; MOVE BOTTOM BOUNDARY UP BY ONE
	JMP	PARTLP		; ONE ELEMENT
;
; THIS PARTITION HAS NOW BEEN SUBDIVIDED INTO TWO PARTITIONS.
; ONE STARTS AT THE TOP AND ENDS JUST ABOVE THE CENTRAL ELEMENT.
; THE OTHER STARTS JUST BELOW THE CENTRAL ELEMENT
; AND CONTINUES TO THE BOTTOM.
; THE CENTRAL ELEMENT IS NON IN ITS PROPER SORTED POSITION
; AND NEED NOT BE INCLUDED IN EITHER PARTITION
;
DONE:
;
; FIRST CHECK WHETHER STACK MIGHT OVERFLOW
; IF IT IS GETTING TOO CLOSE TO THE BOTTOM,
; ABORT THE PROGRAM AND EXIT
;
	TFR	S,D		; CALCULATE SP STKBTM
	SUBD	STKBTM
	BLS	ABORT		; BRANCH (ABORT) IF STACK T00 LARGE
;
; ESTABLISH BOUNDARIES FOR FIRST (LOWER) PARTITION
; LOWER BOUNDARY IS SAME AS BEFORE
; UPPER BOUNDARY IS ELEMENT JUST BELOW CENTRAL ELEMENT
; THEN RECURSIVELY QUICKSORT FIRST PARTITION
				;
	LDY	LAST		; GET ADDRESS OF LAST ELEMENT
	PSHS	X,Y		; SAVE CENTRAL, LAST ADDRESSES
	LEAY	-2,X		; CALCULATE LAST FOR FIRST PART
	LDX	FIRST		; FIRST IS SAME AS BEFORE
	BSR	SORT		; QUICKSORT FIRST PART
;
; ESTABLISH BOUNDARIES FOR SECOND (UPPER) PARTITION
; UPPER BOUNDARY IS SAME AS BEFORE
;

EXITPR:
;
; LOWER BGUNDARY IS ELEMENT JUST ABOVE CENTRAL ELEMENT
; THEN RECURSIVELY QUICKSORT SECOND PARTITION
;
	PULS	X,Y		; GET FIRST, LAST FOR SECOND PART
	LEAX	2,X		; CALCULATE FIRST FOR SECOND PART
	BSR	SORT		; QUICKSORT SECOND PART
	CLC			; CLEAR CARRY, INDICATING NO ERRORS
	RTS	GOOD		; EXIT
;
; ERROR EXIT, SET CARRY TO 1
;
ABORT:
	LDS	OLDSP		; GET ORIGINAL STACK POINTER
	SEC			; INDICATE ERROR
	RTS			; RETURN WITH ERROR INDICATOR TO
				; ORIGINAL CALLER
;*****************************
; ROUTINE:	MEDIAN
; PURPOSE:	DETERMINE WHICH ELEMENT IN A PARTITION
;		SHOULD BE USED AS THE CENTRAL ELEMENT OR PIVOT
; ENTRY:	ADDRESS OF FIRST ELEMENT IN REGISTER X
;		ADDRESS OF LAST ELEMENT IN REGISTER Y
; EXIT:		CENTRAL ELEMENT IN FIRST POSITION
;		X,Y UNCHANGED
; REGISTERS USED:	D,U
; *******************************
MEDIAN:
	;
	; DETERMINE ADDRESS OF MIDDLE ELEMENT
	; MIDDLE := ALIGNED(FIRST + LAST) DIV 2
	;
	PSHS	Y		; SAVE ADDRESS OF LAST IN STACK
	TFR	X,D		; ADD ADDRESSES OF FIRST, LAST
	ADDD	,S
	LSRA			; DIVIDE SUM BY 2
	RORB
	ANDB	#11111110b	; ALIGN CENTRAL ADDRESS
	PSHS	D		; SAVE CENTRAL ADDRESS ON STACK
	TFR	X,D		; ALIGN MIDDLE TO BOUNDARY OF FIRST
	CLRA			; MAKE BIT 0 OF MIDDLE SAME AS BIT
	ANDB	#00000001b	; 0 OF FIRST
	ADDD	,S++
	TFR	D,U		; SAVE MIDDLE ADDRESS IN U
	;
	; DETERMINE MEDIAN OF FIRST, MIDDLE, LAST ELEMENTS
	; COMPARE FIRST AND MIDDLE
	;
	LDD	,U		; GET MIDDLE ELEMENT
	CMPD	,X		; MIDDLE FIRST
	BLS	MIDD1		; BRANCH IF FIRST MIDDLE
	;
	; WE KNOW (MIDDLE > FIRST)
	; SO COMPARE MIDDLE AND LAST
	;
	LDD	,Y		; GET LAST ELEMENT
	CMPD	,U		; LAST MIDDLE
	BCC	SWAPMF		; BRANCH IF LAST MIDDLE
				; MIDDLE IS MEDIAN
	;
	; WE KNOW (MIDDLE > FIRST) AND (MIDDLE > LAST)
	; SO COMPARE FIRST AND LAST (MEDIAN IS LARGER ONE)
	;
	CMPD	,X		; LAST FIRST
	BMI	SWAPLF		;BRANCH IF LAST > FIRST
				; LAST IS MEDIAN
	BRA	MEXIT		; EXIT IF FIRST LAST
				; FIRST IS MEDIAN
				;
	; WE KNOW FIRST MIDDLE
	; SO COMPARE FIRST AND LAST

MIDD1:
	LDD	,Y		; GET LAST 
	CMPD	,X		; LAST FIRST 
	BCC	MEXIT		; EXIT IF LAST > = FIRST
				; FIRST IS MEDIAN
	;
	; WE KNOW (FIRST MIDDLE) AND (FIRST > LAST)
	; SO COMPARE MIDDLE AND LAST (MEDIAN IS LARGER ONE)
	;
	CMPD	,U		; LAST MIDDLE
	BMI	SWAPLF		; BRANCH IF LAST > MIDDLE
				; LAST IS MEDIAN
	;				;
	; MIDDLE IS MEDIAN, MOVE ITS POINTER TO LAST
	;
SWAPMF:
	TFR	U,Y		; MOVE MIDDLE'S POINTER TO LAST
	;
	; LAST IS MEDIAN, SWAP IT WITH FIRST
	;
SWAPLF:
	BSR	SWAP		; SWAP LAST, FIRST
	;
	; RESTORE LAST AND EXIT
	;
MEXIT:
	PULS	Y		; RESTORE ADDRESS OF LAST ELEMENT
	RTS
;
; *******************************
;	ROUTINE:		SWAP
;	PURPOSE:		SWAP ELEMENTS POINTED TO BY X,Y
;	ENTRY:			X = ADDRESS OF ELEMENT 1
;				Y = ADDRESS OF ELEMENT 2
;	EXIT:			ELEMENTS SWAPPED
;
;	REGISTERS USED:		D
; *********************************
SWAP:
	LDD	,X		; GET FIRST ELEMENT
	PSHS	D		; SAVE FIRST ELEMENT
	LDD	,Y		; GET SECOND ELEMENT
	STD	,X		; STORE SECOND IN FIRST
	PULS	D		; GET SAVED FIRST ELEMENT
	STD	,Y		; STORE FIRST IN SECOND ADDRESS
	RTS
;
;	DATA SECTION
;
FIRST:	RMB	2		; POINTER TO FIRST ELEMENT OF PART
LAST:	RMB	2		; POINTER TO LAST ELEMENT OF PART
STKBTM:	RMB	2		; THRESHOLD FOR STACK OVERFLOW
OLDSP:	RMB	2		; POINTER TO ORIGINAL RETURN ADDRESS
;
; SAMPLE EXECUTION
;
;
; PROGRAM SECTION
SC6F:
;
; SORT AN ARRAY BETWEEN BEGBUF (FIRST ELEMENT)
; AND ENDBUF (LAST ELEMENT)
; LET STACK EXPAND 100 HEX BYTES
;
	LEAU	$100,S		; BOUNDARY FOR STACK OVERFLOW
	LDX	#BEGBUF		; ADDRESS OF FIRST ELEMENT
	LDY	#ENDBUF		; ADDRESS OF LAST ELEMENT
	PSHS	U,X,Y		; SAVE PARAMETERS IN STACK
	JSR	QSORT		; SORT USING QUICKSORT
				; RESULT FOR TEST DATA IS
				; 0,1,2,3, ...	,14,15
	BRA	SC6F		; LOOP TO REPEAT TEST
;
; DATA SECTION
;
BEGBUF:
	db	15
	db	14
	db	13
	db	12
	db	11
	db	10
	db	9
	db	8
	db	7
	db	6
	db	5
	db	4
	db	3
	db	2
	db	1
	db	0
ENDBUF:
	db	0
	END