PDA

View Full Version : QuickSort in 6502 assembler



carlsson
October 10th, 2006, 05:00 PM
The first attempt failed, but after changing to a different algorithm, I got QuickSort working
Kind of. I was about to post the code, but I just found if the data to be sorted is too versatile (too big interval between smallest and largest) and at the same time already sorted, my algorithm recurses so many steps I run out of stack space and computer crashes. :-(

I tried to come up with a hackery solution, but so far I came up with no real good workaround. One way would be to take a copy of the whole stack elsewhere, and start a new one, but it is a bit clumsy. I tried to store only the low byte of the return address as long as I stay within the same memory page. It helped a bit, but not fully. Since the recursive calls come from only two places, maybe I can store some counter how many times the return address is valid instead of storing each return address:

Now: ret1 ret1 ret1 ret1 ret2 ret2 ret2 ret1 ret2 ret2 ret1 end (12 bytes)
Idea: 4 ret1 3 ret2 1 ret1 2 ret2 1 ret1 end (11 bytes)

I could probably align the code in a way so I can smart-code the counter into the return address or at least distinguish between the two, but I'd look for a general solution. This is nothing I need to use right now, so it is far from priority, just annoying.

Anyway, this is what I have for now. It would assemble with DASM and execute on a Commodore 64. Address $0400 equals screen matrix, so you can see the data being sorted.


#processor 6502
#seg main

array eqm $0400 ; $c100
larec eqm $c200
rarec eqm $c300
crec eqm $fa
ktmp eqm $fb
lval eqm $fc
left eqm $fd
right eqm $fe

org $0900

lda #$00
sta crec
tax
sta larec,x
lda #$ff
sta rarec,x
jsr quick
rts

quick: ldx crec
lda rarec,x
sta right
lda larec,x
sta left
inc crec

tax ; left
cpx right
bcs qout$ ; if left >= right exit
ldy right
lda array,y
cmp array,x ; if d[left] > d[right]
bcs bprep$
jsr swap
bprep$: lda array,x ; repeat
sta lval
prep$: lda lval
loop$: cpx right
beq loop2$
inx
cmp array,x ; repeat j=j+1 until d[left] <= d[j]
beq loop2$
bcs loop$
loop2$: cpy left
beq uloop2$
dey
cmp array,y ; repeat k=k-1 until d[left] >= d[k]
bcc loop2$
uloop2$: sty ktmp
cpx ktmp ; if k >= j
php
bcs uloop1$
jsr swap
uloop1$: plp
beq prep$
bcc prep$
uprep$: ldx left
jsr swap

ldx crec
lda left
sta larec,x
cpy left
php
dey
tya
sta rarec,x
plp
bcc no1st$
beq no1st$
jsr quick ; jsr
no1st$: ldx crec
ldy rarec,x
iny
iny
tya
sta larec,x
lda rarec-1,x ; lda right
sta rarec,x
jsr quick
qout$: dec crec
rts

;; swap takes x/y as index to the two values to swap
swap: lda array,x
pha
lda array,y
sta array,x
pla
sta array,y
rts


To make it worse (?), I have another code written by someone else that is about the same in size, but functions better. It overcomes the recursive calls, which is something I'd like to do as well. I have some iterative implementation of QuickSort in a C book, but I never was successful to convert it into 6502. Maybe that's the desired approach anyway; stay away from recursion on small platforms.