sort algos for the 6502

[vol]

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 the 21th century. 

Does anybody know about other implementations of fast sorting methods for the 6502?

Edited February 7, 2021 by vol

[dmsc]

Hi!

4 hours ago, vol said:

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 the 21th century. 

Does anybody know about other implementations of fast sorting methods for the 6502?

What?????

 

There are hundred of quicksort implementations for the 8-bit computers.... some old ones:

 

Here: 1986, in BASIC for the Atari: https://archive.org/details/analog-computing-magazine-42/page/n43/mode/2up

Here: 1983, for the Commodore: https://archive.org/details/1983-09-compute-magazine/page/n195/mode/2up

 

Have Fun!

[Irgendwer]

- Deleted -

 

Edited February 7, 2021 by Irgendwer

[vol]

11 hours ago, dmsc said:

Hi!

What?????

 

There are hundred of quicksort implementations for the 8-bit computers.... some old ones:

 

Here: 1986, in BASIC for the Atari: https://archive.org/details/analog-computing-magazine-42/page/n43/mode/2up

Here: 1983, for the Commodore: https://archive.org/details/1983-09-compute-magazine/page/n195/mode/2up

 

Have Fun!

Thank you but your first link gives us quicksort written in Basic.  The second link connects us with a kind of real ML quicksort but there are no sources only a lot of Basic DATA items.  We need to decipher it.  So you are rather wrong about hundreds implementations for the 6502 which we can directly use for instance in the Atari 800, I doubt that you can find only one.

[777ismyname]

It is very easy to find many sort algorithms for the Atari. Compute published several machine language versions with program listings. There were quite a few other listings, too. A quick search at atariarchives dot org, atarimagazines dot com, atarimania, et al will yield quite a few. I haven’t looked at them in ages, but succinctly recall one of the Compute compendiums having the machine language code listed for some sorting algorithm. 
 

 

 

[vol]

On 2/9/2021 at 8:40 AM, 777ismyname said:

It is very easy to find many sort algorithms for the Atari. Compute published several machine language versions with program listings. There were quite a few other listings, too. A quick search at atariarchives dot org, atarimagazines dot com, atarimania, et al will yield quite a few. I haven’t looked at them in ages, but succinctly recall one of the Compute compendiums having the machine language code listed for some sorting algorithm. 
 

 

 

Thank you.  I have done some searches and found almost nothing.  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.

Edited February 11, 2021 by vol

[777ismyname]

If I remember, I will ask the guys in a retro Zoom meeting we are having tomorrow if they know of sorting algorithms. Past that, I will look through some of the Holmes disks and see if anything pops up.

 

Sorting is about the first real software thing I remember studying in my first computer class 40 years ago. 

[+gnusto]

On 2/7/2021 at 7:00 AM, vol said:

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 the 21th century.

 

In my apparently endless research for making a decent front end experience in Launchbox for Atari 8 bits, I ran across this : "SuperSort" from APX, sold in 1981, which was a Quicksort implementation in asm based on it's own description.

[vol]

On 2/20/2021 at 6:18 AM, 777ismyname said:

Sorting is about the first real software thing I remember studying in my first computer class 40 years ago. 

 I has been able to decipher, test, and improve Ultrasort and Lightningsort that were published in Compute 40 and 52.  The latter issue contains variants for the Commodore 64, VIC-20, Apple II, and IBM PC.  However there is no variant for the Atari 800. I can think that the author just was not able to conceive the way which requires for the work with Atari Basic strings. 
I am also less familiar with the Atari 8-bit architecture than the Commodore.  So I could make only a program for the C64.  The results are here
If somebody wants to port the program to the Atari I am ready to provide any help.

On 3/9/2021 at 7:13 AM, gnusto said:

 

In my apparently endless research for making a decent front end experience in Launchbox for Atari 8 bits, I ran across this : "SuperSort" from APX, sold in 1981, which was a Quicksort implementation in asm based on it's own description.

Do you know where can I get it?

[+DjayBee]

59 minutes ago, vol said:

Do you know where can I get it?

This one?

http://www.atarimania.com/list_utilities_atari_search_115.117.112.101.114.115.111.114.116._8_U.html

https://www.atarinside.com/blog/index.php/atarinside-items/super-sort/

 

 

Supersort (1983)(Atari)(DE).atr

[vol]

On 6/16/2021 at 11:36 AM, DjayBee said:

This one?

http://www.atarimania.com/list_utilities_atari_search_115.117.112.101.114.115.111.114.116._8_U.html

https://www.atarinside.com/blog/index.php/atarinside-items/super-sort/

 

 

Supersort (1983)(Atari)(DE).atr 90.02 kB · 5 downloads

Thank you very much for these links.
I have checked the ATX Supersort.  This year is the 40th anniversary of the date when Supersort was published.  This program appeared 3 years before the best C64 sorting program (Lightningsort) was published and it was about 10-15% faster!  The latter is caused by insertionsort optimization.  I thought I could make much faster code but I was able to get only small advantage.  However my sort routine is never quadratic, so for some rare cases it can be much faster.  Supersort is quadratic for ordered or nearly ordered data.
I have to confess I didn't expect that old software from 1981 can be so good.  I only miss good programs that allow us to test a large array of strings.  Therefore I wrote two programs to fill this gap, TSORT2 and TSORT3 for Supersort rev 2 and 3 respectively.  I attached them to this post.  Just boot from a proper Supersort disk and type ENTER"drive:TSORT2.LST" or ENTER"drive:TSORT3.LST".

 

tsort.zip

Edited June 23, 2021 by vol

[Heaven/TQA]

Have you looked at codebase64?

[vol]

On 6/27/2021 at 3:44 PM, Heaven/TQA said:

Have you looked at codebase64?

Of course, I even contributed some algorithms there.  

[vol]

Maybe it can be interesting that Lightningsort for the C64 is buggy - details are here - this subtle bug is caused by the improper use of zp locations, so Lightningsort implementations for the Apple II and IBM PC may be correct.

Anyway we just got that the count of known quicksort implementations for the 6502 has decremented to 3: Atari Supersort (1981), C64 Ultrasort (1983), and C64/C+4 Enhancedsort (2021).

[zbyti]

https://github.com/litwr2/6502-sorting

 

https://github.com/litwr2/6809-sorting

Edited August 8, 2021 by zbyti