*	Lab5.asm
*		Bubble Sort
*		Mike Dawdy

*	Identifiers:
*		Array			RAM bytes		contains data to be sorted
*		ArrayEnd		equate			pointer to end of array
*		NumElements	equate			number of array elements
*		Passes			RAM byte		at most NumElements-1
*		i				Register X	pointer to next element
*		NumCompares	Register Y	decrement each pass
*		Swap			RAM bit		true if swap done during a pass
*		Temp			RAM byte		Temporary storage

*	Algorithm:
*		[basic algorithm with 2 efficiencies incorporated]
*		make at most NumElements - 1 passes thru the array
*		on each pass compare successive pairs
*		if in decreasing order swap and set Swap to True
*		on the next pass make 1 fewer comparisons
*		done when Swap is false or NumElements-1 passes completed


*Program		equ		$c000	;load and start address for program
Program		equ		$2000

*LocalData	equ		$c100	;address for start of data
LocalData	equ		$0000

Registers	equ		$1000
EOT     	equ		$04			;End Of Text, for BUFFALO
OutString	equ		$ffc7		;BUFFALO routine to display text

	org		LocalData

Array:		dc.b	$44, $6f, $75, $67, $53, $74, $65, $77, $61, $72, $74, EOT
ArrayEnd	equ		*-1

NumElements		equ		ArrayEnd-Array
NumElementsM1	equ		ArrayEnd-Array-1

Swap:		ds.b	1
Passes:	ds.b	1
Temp:		ds.w	1


	org		Program

	ldx		#Array			;display unsorted data
	jsr		OutString

	jsr		Sort

	ldx		#Array			;display sorted data
	jsr		OutString

	swi						;logical end of program

Sort:
	ldy		#NumElements		;Y = number of compares next pass
	bset	Swap,#$01			;early exit if no swaps done
	ldaa	#NumElementsM1	;count down from max number of passes
	staa	Passes

OuterLoop:
	brclr	Swap,#$01,SortDone		;no swaps => sort is done
	brclr	Passes,#$ff,SortDone	;Passes = 0 => sort is done

	bclr	Swap,#$01		;assume there will be no swaps
	ldx		#$0000			;let X point to 1st array element
	dey						;1 less compare each pass
	sty		Temp

InnerLoop:
	cpx		Temp			;InnerLoop done when X == Y [Temp]
	beq		InnerLoopDone

	ldaa	Array,X		;compare current item with next
	cmpa	Array+1,X
	bls		NoSwap

	ldab	Array+1,X		;swap [Array+0] with [Array+1]
	staa	Array+1,X
	stab	Array,X
	bset	Swap,#$01		;indicate a swap has been done

NoSwap:
	inx						;let X point to next array item
	bra		InnerLoop

InnerLoopDone:
	dec		Passes
	bra		OuterLoop
	
SortDone:	
	rts