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

Date view Thread view Subject view

From: Groepaz (
Date: 2003-03-05 16:06:25

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 one 
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 spread) 
arrays at maximum speed...atleast in a game or demo atleast. actually i cant 
remember offhand where i would use anything but a bubblesort (because of easy 
and small implementation), except for a sprite-multiplexer (most ppl use a 
combination of shellsort and bubblesort here). things that arent 
speed-critical at all (sorting hiscorelist is prime example) often even use 
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 implemented 
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 the 
start of current line (=carriage return).
2) keep in mind that the conio routienes can not handle scrolling the screen 
when you print beyond the bottom of the that case it will just 
crash. (most likely, atleast behave funny :o))

> 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 out.... 
however the reason for a program no more working when started twice is that 
the initialized data section is kept only once in memory. ie, if you rerun 
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 slightly 
modified crt0.s and linkerscript, but it will result in (depending on size of 
your data section) enormous waste of memory. (because most programs arent 
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.

Date view Thread view Subject view

This archive was generated by hypermail 2.1.3 : 2003-03-05 16:45:14 CET