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.

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.