I’ve been on a bit of a sorting kick lately. Maybe sorting garbage on the screen is a proxy for finding order in my own life. Or maybe it’s just fun. I’m going with the latter.
The following code runs bubble sort, insertion sort, and quick sort, and displays the timing using TIMVAL from the BASIC ROM. In between each phase, hit a key on the keyboard to continue.
The code is split into two files, with the first one INCLUDE’ing the second one via the LWASM pseudo-op.
An interesting extension to try… sort garbage in other display modes. High-res display modes take up more space, and thus might help increase the quick sort time enough that you can actually see it do something. 😃
QS.ASM
; Quick Sort and friends
ORG $4000
SortScrnBufStart EQU $E00 ; Garbage / sort screen start address
TimingScrnBufStart EQU $400 ; Timing info screen start address
ScrnBufSize EQU $200 ; Num bytes in either screen
POLCAT EQU $A000
RND EQU $BF1F ; ROM routine to generate random number
INTCNV2 EQU $B3FE ; ROM routine to convert FPA0 to int, without the overflow check
VALTYP EQU $6 ; Flag: 0=numeric, $FF=string
TIMVAL EQU $112 ; Location of BASIC's TIMER (2 bytes)
; Location of first byte of floating point accumulator
FP0EXP EQU $4F
; Values to fill floating point accumulator as parameter to
; pass to RND as the max random integer (65536)
EXPVAL EQU $91
MANVAL EQU $80
SGNVAL EQU $7F
; ---------------------------------------------------------------
; main
; ---------------------------------------------------------------
LBSR PrepareStrings ; Run TweakLowerCaseLetters on label strings
MainLoop:
LBSR ScreenBufE00 ; Show sorting screen
; Bubble Sort
LBSR InitBufferAndSortScreen ; Generate random garbage, store & display
BSR WaitForKeystroke
LDD #0 ; Reset timer
STD TIMVAL
LBSR BubbleSort
LDD TIMVAL ; Add elapsed time to timing info
LDX #TimingInfo
ADDD ,X
STD ,X
BSR WaitForKeystroke
; Insertion sort
LBSR InitSortScreen ; Replace random garbage
BSR WaitForKeystroke
LDD #0 ; Reset timer
STD TIMVAL
LBSR InsertionSort
LDD TIMVAL ; Add elapsed time to timing info
LDX #TimingInfo+2
ADDD ,X
STD ,X
BSR WaitForKeystroke
; Quick sort
LBSR InitSortScreen ; Replace random garbage
BSR WaitForKeystroke
LDD #0 ; Reset timer
STD TIMVAL
LDD #SortScrnBufStart ; Param 1: Start of list
PSHS D
LDD #SortScrnBufStart+ScrnBufSize-1 ; Param 2: End of list
PSHS D
LBSR QuickSort
LEAS 4,S
LDD TIMVAL ; Add elapsed time to timing info
LDX #TimingInfo+4
ADDD ,X
STD ,X
; End of trial
INC NumTrials ; Just finished a new trial
LBSR UpdateTimingsScreen ; Fill timing screen with new times
BSR WaitForKeystroke
LBSR ScreenBuf400 ; Show timings screen
BSR WaitForKeystroke
BRA MainLoop ; Repeat for another trial
; ---------------------------------------------------------------
; WaitForKeystroke sub
; ---------------------------------------------------------------
WaitForKeystroke:
JSR [POLCAT] ; Any keystoke?
BEQ WaitForKeystroke ; If not, loop
RTS
; ---------------------------------------------------------------
; QuickSort(lo, hi) sub
; Performs a recursive 3-way partitioning quick sort.
; Middle partition contains all elements equal to pivot
; First and third partitions contain elements less than
; and greater than the pivot, respectively.
; Pivot value initially at *lo. It slides right during the
; partitioning phase. Then recurse on left side (before
; pivot) and then on right side (after pivot)
; Parameters: lo & hi are addrs of beginning and end of list to sort
; Entry: Stack: lo (2 bytes), hi (2 bytes), PC <-- S
; Register usage:
; X = lt (beginning of middle partition--earlier elements LessThan pivot)
; Y = gt (end of middle partition--later elements GreaterThan pivot)
; U = i (current element addr / "cursor"),
; B = *i (current element value)
; A = scratch
; ---------------------------------------------------------------
QuickSort:
LDX 4,S ; X = lt = lo
CMPX 2,S ; lo < hi ?
BHS QSDone ; no, done (base case)
LDY 2,S ; Y = gt = hi
LDA ,X ; A = pivot = *lo
STA Pivot ; Store pivot value for use in comparisons
LEAU ,X ; i = lo
PartitionLoop:
STU i ; Temporarily store i so we can use it in a comparison
CMPY i ; gt >= i ?
BLO PartitionLoopDone ; no, exit loop
LDB ,U ; B = *i (current element to compare with pivot)
CMPB Pivot ; compare current element (B) with pivot
BLO LessThanPivot
BHI GreaterThanPivot
; case: B == pivot
; Just advance i
LEAU 1,U ; i++
BRA PartitionLoop
LessThanPivot:
; case: B < pivot
; Exchange *lt & *i, advance both lt & i
LDA ,X ; A = *lt (B is already *i)
STA ,U+ ; Exchange part 1: *lt -> *i; i += 1
STB ,X+ ; Exchange part 2: *i -> *lt; lt += 1
BRA PartitionLoop
GreaterThanPivot:
; case: B > pivot
; Exchange *i & *gt, decrement gt
LDA ,Y ; A = *gt (B is already *i)
STB ,Y ; Exchange part 1: *i -> *gt
LEAY -1,Y ; gt -= 1; see note (*) below
STA ,U ; Exchange part 2: *gt -> *i
BRA PartitionLoop
PartitionLoopDone:
; All elements between lt and gt are the same
; Recurse on the remaining two portions (<lt and >gt)
LEAX -1,X ; lt -= 1
LDD 4,S ; D = lo
PSHS Y ; Save gt for use after first recursive call
; First recursive call: QS(lo, lt-1)
PSHS D ; Push param 1 (new lo = old lo)
PSHS X ; Push param 2 (new hi = old lt - 1)
BSR QuickSort ; Recurse on region [lo;lt-1]
LEAS 4,S ; PULS the parameters
PULS Y ; Restore gt; S now restored to same addr as on entry
LEAY 1,Y ; gt += 1
LDD 2,S ; D = hi
; Second recursive call: QS(gt+1, hi)
PSHS Y ; Push param 1 (new lo = old gt + 1)
PSHS D ; Push param 2 (new hi = old hi)
; (above pushes can be combined into single PSHS but isn't this confusing enough?)
BSR QuickSort ; Recurse on region [gt+1;hi]
LEAS 4,S ; PULS the parameters
QSDone:
RTS
i RMB 2 ; Addr of current element to compare with pivot
Pivot RMB 1 ; Value of pivot. Its addr starts at lo==lt, and as pivot moves up, lt updates to point to it
; (*) Above we did two separate ops:
; STB ,Y
; LEAY -1,Y
; This stores B into Y and then decrements Y.
; A shortcut might be:
; STB ,Y-
; where the decrement happens AFTER the store.
; But all auto-decrements happen BEFORE the store / load
; and all auto-increments happen AFTER the store / load.
; No post-decrement or pre-increment exists.
; As an alternative, one might try:
; STB 1,-Y
; which does a pre-decrement but then adjusts for
; it by using 1 as the index when storing B. However,
; you cannot mix auto-inc/dec with an index. So it seems
; I'm stuck having to do two separate ops.
; ---------------------------------------------------------------
; BubbleSort sub
; Adapted from TRS-80 Color Computer Assembly Language Programming
; by William Barden, Jr.
; ---------------------------------------------------------------
BubbleSort:
LDX #SortScrnBufStart
LDU #0 ; Reset change flag to 0
ProcessPair:
LDA ,X+ ; Get first entry
CMPA ,X ; Compare with second
BLS EndProcessPair ; No need to swap
LDB ,X ; Get second entry
STB -1,X ; Swap second to first
STA ,X ; Swap first to second
LDU #1 ; Set change flag to 1
EndProcessPair:
CMPX #SortScrnBufStart+ScrnBufSize-1 ; Test for end of pass
BNE ProcessPair ; Continue pass
CMPU #0 ; Pass complete; test change flag
BNE BubbleSort ; There was a change; do another pass
RTS
; ---------------------------------------------------------------
; InsertionSort sub
; X: outer loop variable, starts at second element, continues
; forward through the list. Points to current item to
; consider shifting left
; U: inner loop variable, starts at X, and shifts left
; ---------------------------------------------------------------
InsertionSort:
LDX #SortScrnBufStart+1 ; First item to consider is SECOND item
ISOuterLoop:
CMPX #SortScrnBufStart+ScrnBufSize ; Has X reached the end?
BHS ISDone ; Yes, done with entire sort
TFR X,U ; Init inner loop: U starts at X
ISInnerLoop:
CMPU #SortScrnBufStart ; Have we shifted all the way to the beginning?
BEQ ISInnerLoopDone ; Yes, inner loop is done
LDA ,U ; A is value we are shifting left
CMPA -1,U ; Compare A with its left neighbor
BHS ISInnerLoopDone ; A > left neighbor, no need to shift
LDB -1,U ; B is left-neighbor of A
STA -1,U ; Swap right to left
STB ,U ; Swap left to right
LEAU -1,U ; Move U left to continue the shifting
BRA ISInnerLoop
ISInnerLoopDone:
LEAX 1,X ; Advance X to next item to consider for shifting
BRA ISOuterLoop
ISDone:
RTS
; ---------------------------------------------------------------
; InitSortScreen sub
; Copies random garbage from GbgBuffer to the text screen
; buffer starting at $E00
; ---------------------------------------------------------------
InitSortScreen:
LDU #GbgBuffer ; Source
LDX #SortScrnBufStart ; Destination
InitSortScreenLoop:
CMPX #SortScrnBufStart+ScrnBufSize
BHS InitSortScreenLoopDone
LDD ,U++
STD ,X++
BRA InitSortScreenLoop ; Loop up
InitSortScreenLoopDone:
RTS
; ---------------------------------------------------------------
; TwoRandomBytes sub
; ---------------------------------------------------------------
TwoRandomBytes:
; Initialize floating point accumulator
LDX #FP0EXP
LDA #EXPVAL
STA ,X+ ; Set FP0EXP
LDA #MANVAL
STA ,X+ ; Set byte 1 of mantissa
LDD #0
STD ,X++ ; Clear bytes 2-3 of mantissa
STA ,X+ ; Clear byte 4 of mantissa
LDA #SGNVAL
STA ,X+ ; Set FP0SGN
; Clear rest of FPA0 (7 bytes: COEFCT, STRDES, FPCARY)
LDD #0
STD ,X++
STD ,X++
STD ,X++
STA ,X
JSR RND ; Call RND(FPA0), answer in FPA0
LDA FP0EXP ; Check to see if RND returned 65536
CMPA #$91
BNE FPA0ToInt ; No. Do INTCNV2 with no fear of overflow
LDD #0 ; Yes. Wraparound to 0 and we're done
RTS
FPA0ToInt:
CLR VALTYP ; Set value type to numeric
JSR INTCNV2 ; FPA0 -> D
RTS
; ---------------------------------------------------------------
; InitBufferAndSortScreen sub
; Fills screen buffer starting at $E00 with random garbage,
; and keeps a copy of the same garbage in GbgBuffer for
; use in successive sorts
; ---------------------------------------------------------------
InitBufferAndSortScreen:
BSR ActivateDispMode ; Activate alphanumeric mode
LDX #SortScrnBufStart
LDU #GbgBuffer
GarbageScreenLoop:
CMPX #SortScrnBufStart+ScrnBufSize
BHS GarbageScreenLoopDone
PSHS X,U ; Fill another 2 bytes of garbage
BSR TwoRandomBytes
PULS X,U
STD ,X++
STD ,U++
BRA GarbageScreenLoop ; Loop up
GarbageScreenLoopDone:
RTS
; ---------------------------------------------------------------
; ActivateDispMode sub
; Configures VDG for alphanumeric / semigraphic mode
; Start address configured elsewhere
; ---------------------------------------------------------------
ActivateDispMode:
; Set SAM control bits (to determine screen buffer size)
; $FFC0,$FFC2,$FFC4
LDY #$FFC0
STA ,Y++
STA ,Y++
STA ,Y
; Set VDG operating mode ($0 for AI)
CLRA
STA $FF22
RTS
; ---------------------------------------------------------------
; ScreenBufE00 sub
; Set screen buffer start address to $E00
; This displays the sorting screen
; ---------------------------------------------------------------
ScreenBufE00:
STA $FFCB
STA $FFC9
STA $FFC7
RTS
; ---------------------------------------------------------------
; ScreenBuf400 sub
; Set screen buffer start address to $400
; This displays the timings screen
; ---------------------------------------------------------------
ScreenBuf400:
STA $FFCA
STA $FFC9
STA $FFC6
RTS
; ---------------------------------------------------------------
; PrepareStrings sub
; Call TweakLowerCaseLetters for all static strings
; ---------------------------------------------------------------
PrepareStrings:
LDX #NumTrialsLbl
BSR TweakLowerCaseLetters
LDX #BubLbl
BSR TweakLowerCaseLetters
LDX #InsLbl
BSR TweakLowerCaseLetters
LDX #QuickLbl
BSR TweakLowerCaseLetters
RTS
; ---------------------------------------------------------------
; UpdateTimingsScreen sub
; Redraw timings screen with latest timing info
; ---------------------------------------------------------------
UpdateTimingsScreen:
LDX #TimingScrnBufStart ; Clear
BSR ClearScreen
LDX #NumTrialsLbl ; Num trials label
LDU #TimingScrnBufStart
BSR PrintString
LDB NumTrials ; Num trials value (only 1 byte!)
CLRA
LDU #TimingScrnBufStart+(1*32)
BSR PrintInt
LDX #BubLbl ; Bubble sort label
LDU #TimingScrnBufStart+(4*32)
BSR PrintString
LDD TimingInfo ; Print Bubble Sort timing
LDU #TimingScrnBufStart+(5*32)
BSR PrintInt
LDX #InsLbl ; Insertion sort label
LDU #TimingScrnBufStart+(8*32)
BSR PrintString
LDD TimingInfo+2 ; Print Insertion Sort timing
LDU #TimingScrnBufStart+(9*32)
BSR PrintInt
LDX #QuickLbl ; Quick Sort label
LDU #TimingScrnBufStart+(12*32)
BSR PrintString
LDD TimingInfo+4 ; Print Quick Sort timing
LDU #TimingScrnBufStart+(13*32)
BSR PrintInt
RTS
; ---------------------------------------------------------------
; General routines for printing strings and numbers
INCLUDE PrintUtilities.asm
; ---------------------------------------------------------------
; ---------------------------------------------------------------
; Symbols / data
; ---------------------------------------------------------------
GbgBuffer RMB ScrnBufSize ; Random garbage storage
NumTrials FCB 0
NumTrialsLbl FCN "number of trials:"
BubLbl FCN "bubble sort:"
InsLbl FCN "insertion sort:"
QuickLbl FCN "quick sort:"
; Array of timing sums
TimingInfo FDB 0,0,0 ; Two bytes for each of 3 sorting algorithms
END $4000
PrintUtilities.asm
INTCNV EQU $B3ED ; ROM routine to convert int in FPA0 to D
FPSCNV EQU $BDD9 ; ROM routine to convert FPA0 to ASCII string
GIVABF EQU $B4F4 ; ROM routine to convert D to FPA0
STRBUF EQU $03D7 ; Start of BASIC string buffer
; ---------------------------------------------------------------
; TweakLowerCaseLetters sub
; Adjusts all bytes representing lower-case letters in the
; specified string in the same manner as BASIC ROM's PUTCHR.
; Running this once on a string allows later code to directly
; store the resulting string's bytes in the screen buffer
; and have the lower-case letters show up properly. All
; non-lower-case-letter characters are left alone, so
; ensure they're adjusted if necessary elsewhere
; Entry: X -> null-terminated string to tweak
; Uses: A
; ---------------------------------------------------------------
TweakLowerCaseLetters:
LDA ,X+
; At the null-teminator?
TSTA
BEQ TweakLowerCaseLettersDone
; In lower-case letter range?
CMPA #'a'
BLO TweakLowerCaseLetters
CMPA #'z'
BHI TweakLowerCaseLetters
; We have a lower-case letter, so perform both tweaks
ANDA #$DF
EORA #$40
STA -1,X ; Store tweaked version
BRA TweakLowerCaseLetters
TweakLowerCaseLettersDone:
RTS
; ---------------------------------------------------------------
; ClearScreen sub
; Clears screen to the super-cool green-on-black
; Assumes screen buffer size is $200
; Entry: X->beginning of screen buffer
; Also uses D
; ---------------------------------------------------------------
ClearScreen:
STX SCRNEND ; Calculate and store SCRNEND
LDD #$200
ADDD SCRNEND
STD SCRNEND
LDD #" " ; Double-space
ClearScreenLoop:
CMPX SCRNEND
BHS ClearScreenDone
STD ,X++
BRA ClearScreenLoop
ClearScreenDone:
RTS
SCRNEND RMB 2
; ---------------------------------------------------------------
; PrintInt sub
; D = int to print
; U = location in screen buffer to print int
; ---------------------------------------------------------------
PrintInt:
PSHS U
JSR GIVABF ; D -> FPA0
JSR FPSCNV ; Convert FPA0 to ASCII string in STRBUF
LDX #STRBUF+3
PULS U
BSR PrintString
RTS
; ---------------------------------------------------------------
; PrintString
; Prints null-terminated string
; Entry: X -> string
; Entry: U -> Screen buffer location to print to
; Also uses: A
; ---------------------------------------------------------------
PrintString:
LDA ,X+
TSTA
BEQ PrintStringEnd ; Break out of loop on terminating null
STA ,U+ ; Print character
BRA PrintString
PrintStringEnd:
RTS
Coco Town 