Recent posts about sort routines got me thinking about an idea I had a while back. The idea came from me being too lazy to figure out the normal sorting methods. So last night I finally put together a working routine.
I can't imagine I'm the first to think of it, but I haven't seen it before.
The basic idea: Instead of comparing and swapping, use a whole page of counters to keep track of how many times each value appears in the unsorted data. The example below uses 1 page of 8 bit counters, but it could use 16 bit counters to sort a much larger list.
The example sorts 256, 8 bit elements...
Code:
unsorted = somewhere
counters = elsewhere ; must be page aligned.
finished = could overwrite unsorted ; must be page aligned.
ldx #0
clr stx counters ; Clear counters before sort.
inc clr+1
bne clr
sort ldx unsorted,y
inc counters,x ; Now it's basically sorted, and for some
iny ; purposes this might be better than
bne sort ; a finished, sorted list.
Some applications might not need the next part. As soon as the counters are set, you can check if a number is there or not, without searching. You can see how many times a number appears, without counting.
But if the finished list is needed, just run through the "counter page" and write out the elements.
For example...
Code:
loop ldx counters,y ; .y is already $00 (from exiting the routine above)
beq no
rpt sty finished ; (Could overwrite unsorted list)
inc rpt+1 ; This is self-modifying and needs to be page aligned. This can
dex ; be changed, but I'm going for shortest & fastest.
bne rpt ; Repeat elements that appear more than once in unsorted list.
no iny
bne loop
SPEED: I haven't actually calculated or compared it to anything, but it seems fast to me. Have to consider that the counters need to be cleared before every sort.
It can sort very large lists using only 2 pages for counters.
On a normal 6502 system, it can't be made to sort 16 bit numbers.
I know the example routine would fail if all 256 elements had the same value, but that's just to simplify the example.
Not using the accumulator at all was just to impress myself. In real life I'd use it in the part that clears the counters, for some speed up. Then that page wouldn't need to be page aligned.
Take away the self modifying code and then nothing needs to be aligned.
Unfortunately, it doesn't run any faster if the unsorted data isn't very unsorted.
Lime Mack Grime.
Login
Register
FAQ
Search
