Posted By
Litwr
on 2021-02-07
10:21:52
|  sort algos for the 6502
I have implemented several known sort algorithms for the 6502. It is an open github project. I dare to think it is likely that a quicksort implementation there is maybe among the first known. It is odd that quicksort was not realized for 8-bit processors until the second decade of 21th century.
|
|
Posted By
Mad
on 2021-02-07
21:54:20
| Re: sort algos for the 6502
Wow cool.. Nice to have these implementations!
Cannot believe a quicksort was not implemented already on 6502..
I love the radix8! :)
|
|
Posted By
Stinaris
on 2021-02-09
04:15:09
 | Re: sort algos for the 6502
Sorry to burst your bubble.
From 2006
http://www.vcfed.org/forum/archive/index.php/t-4687.html
Also I wrote several sort algorithms at school in 6502 in Computer Studies on the BBC Micro including QuickSort in ............ 1985.
These algorithms were part of the curriculum when Computer Studies wasn't about Microsoft products.
|
|
Posted By
Litwr
on 2021-02-11
05:52:20
| Re: sort algos for the 6502
Thank you. Indeed there are several quicksort implementations for the 6502 we can find on net. I have been able to find Ultrasort for various 8-bit Commodores and its improvement Lightning sort. However the latter is not available in texts, only in scans. There are several more quicksorts for the 6502 published after 2005 but all of them have some drawbacks which reduce their usability.
My quicksort implementation is safe so it never crashes your stack and it is never quadratic.
|
|
Posted By
Mad
on 2021-02-11
22:44:06
| Re: sort algos for the 6502
I know it's off topic.. But if you want to sort a larger amount of entities (e.g. Sprites), lft has a good article about "field sort"..
It's actually just a longer list of iny commands where the opcodes are changed e.g. to jmp $c8c8 to collect the items on that position, so it collects all items one after the other.. It's a pretty cool trick and perhaps improvable by a simple hash collision scheme. But nevertheless it's not about sorting numbers, more about entities (e.g. by their screen position)..
It's actually some sort of a bucket sort, but very fast.
https://www.linusakesson.net/programming/fieldsort/index.php
If you do two passes of this sorting,as with any bucket sort,using 256 iny in this case, sorting first by the lowbyte and then sorting by the hibyte you could even sort 16 bit values..
|
|
Posted By
Litwr
on 2021-02-12
02:54:02
| Re: sort algos for the 6502
Thank you for this link. Indeed the bucket/radix sorts are fast but they have several drawbacks:
1) they require memory for a copy of sorted array - we don't need such copy only if we sort little values like bytes, 4-bit nibbles, etc;
2) they need an additional array, for example the radix-8 sort requires 512 bytes for such an array;
3) if we need to sort long multi-byte values we need to do several passes and this slows down sorting, for example the radix/bucket sorts are faster on 32-bit integers on a modern computer but it is slower than quicksort on 128-bit integers;
4) they are difficult to adapt to various types of data.
A man claimed that he implemented a general bucket/radix kind sort for the 6502 - http://forum.6502.org/viewtopic.php?f=2&t=4228#p48897 - but I didn't check his code.
|
|
