From: Groepaz (groepaz_at_gmx.net)
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 screen....in 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) gpz ---------------------------------------------------------------------- To unsubscribe from the list send mail to majordomo_at_musoftware.de with the string "unsubscribe cc65" in the body(!) of the mail.
This archive was generated by hypermail 2.1.3 : 2003-03-05 16:45:14 CET