RE: [cc65] Finished product: FAST ShellSort demo for c64 (working :) ) - feedback?

Date view Thread view Subject view

From: Greg Long (
Date: 2003-03-05 17:21:54

You hit the nail on the head with crashing after scrolling...try it!
Sounds like a direct call to CHROUT ($FFD2) with #$0D in the accumulator
is the best solution.

True, small data sorts don't need this efficiency. High-Score List?  You
mean people are writing GAMES for the 64 instead of viable business and
web applications? ;)

Binary Insert sort works well for already sorted data.

I didn't work with the quicksort much other than to implement it for a
requirement.  I figured the recursive calls would kill the tiny 6502
stack, but that was more of a gut feeling than a scientific test...maybe
it wouldn't.  Quick Sort could be written iteratively, too, it was
pointed out to me.

My goal was to demonstrate the speed difference betwen BASIC and cc65
compiled code (about 20x+ in this "real world" example) and a "typical"
1ghz Win32 machine today.

The comment on operator overloading was a joke :)  I'm getting spoiled
by C++.  ANSI string objects are cool too, but that's a potentially
large object to return on the 6502 in a function call in a loop.

That's nice to know about running apps more than once.  Yes, much of the
"professional" code was never intended to exit out to basic without a
call to 64738 to reset.  PaperClip64 did this - which was probably one
of the most professional packages developed for the 64.

I wish I still have my Westwood BBS source code.  It was a heavily
modified "HAL9000" BBS, with time and date stamp implemented, along with
a bunch of other remote sysop goodies  - as I was a remote sysop for 3
years ;)

Thanks for the feedback and comments,

-----Original Message-----
From: [] On
Behalf Of Groepaz
Sent: Wednesday, March 05, 2003 7:06 AM
Subject: Re: [cc65] Finished product: FAST ShellSort demo for c64
(working :) ) - feedback?

On Wednesday 05 March 2003 04:09, Greg Long wrote:
> The Shell Sort, invented by Donald Shell, is one of the fastest 
> sorting routines available. Others, such as the Quick Sort, involve 
> too much recursion to be practical on the 64. The Merge and Quick sort

> algorithms are faster, but waste memory...up to twice the ammount of 
> the original array.

mmmh, the testsuite i am working on contains a quicksort implementation 
actually :O)

in practice i have never seen anything but "bubble sort" and "straight 
insertion" though....maybe a little bit of heap-sort or shell-sort with
of the previous ones in a last pass. on c64 you would mostly want an 
algorithm that sorts small, mostly "pre-sorted" (not entire random
arrays at maximum speed...atleast in a game or demo atleast. actually i
remember offhand where i would use anything but a bubblesort (because of
and small implementation), except for a sprite-multiplexer (most ppl use
combination of shellsort and bubblesort here). things that arent 
speed-critical at all (sorting hiscorelist is prime example) often even
the least efficient straight insertion :)

> It can be seen that this routine can be modifed to sort strings 
> without much difficulty.  (Now how do I overload the < and > operators

> in C?)

you dont :) overloading is a C++ feature... use strcmp() instead. you
may also 
look at the c-standard library and how the quicksort thing is
there using functionpointers for that problem.

> 1) cprintf does not appear to work properly :  replace \r with \n and 
> watch the results.

it does for pretty damned sure work right :o)

1) as magervalp said, you should use "\n" AND "\r" when working with
conio. \n 
goes to a new line (practically same as "cursor down") and \r goes to
start of current line (=carriage return).
2) keep in mind that the conio routienes can not handle scrolling the
when you print beyond the bottom of the that case it will
crash. (most likely, atleast behave funny :o))

T 2) If the code is executed a second time, it crashes.  Don't know 
> why...It may be due to the writing to RAM beneath the BASIC 
> interpreter. I went with 19,000 integers because in a BASIC routine, 
> that was the most that would fit in the standard 38,911 bytes 
> available.  Does CCS65 modify and make calls to the BASIC interpreter?

it calls the kernal, but not the basic-interpreter which is banked
however the reason for a program no more working when started twice is
the initialized data section is kept only once in memory. ie, if you
the program it will start with values that might eventually have been 
modified in the previous run...which again may result in unexpected 
behaviour. you can probably get around this limitation by creating a
modified crt0.s and linkerscript, but it will result in (depending on
size of 
your data section) enormous waste of memory. (because most programs
expected to be run more than once)

To unsubscribe from the list send mail to with
the string "unsubscribe cc65" in the body(!) of the mail.

To unsubscribe from the list send mail to with
the string "unsubscribe cc65" in the body(!) of the mail.

Date view Thread view Subject view

This archive was generated by hypermail 2.1.3 : 2003-03-05 17:22:46 CET