Omnimaga
Calculator Community => TI Calculators => ASM => Topic started by: Galandros on November 13, 2010, 09:31:32 am
-
While doing some research for WikiTI I have found this: http://frank_y.scripts.mit.edu/pages/z80qsort/
Here is the code for quicksort:
;
; >>> Quicksort routine v1.1 <<<
; by Frank Yaul 7/14/04
;
; Usage: bc->first, de->last,
; call qsort
; Destroys: abcdefhl
;
qsort: ld hl,0
push hl
qsloop: ld h,b
ld l,c
or a
sbc hl,de
jp c,next1 ;loop until lo<hi
pop bc
ld a,b
or c
ret z ;bottom of stack
pop de
jp qsloop
next1: push de ;save hi,lo
push bc
ld a,(bc) ;pivot
ld h,a
dec bc
inc de
fleft: inc bc ;do i++ while cur<piv
ld a,(bc)
cp h
jp c,fleft
fright: dec de ;do i-- while cur>piv
ld a,(de)
ld l,a
ld a,h
cp l
jp c,fright
push hl ;save pivot
ld h,d ;exit if lo>hi
ld l,e
or a
sbc hl,bc
jp c,next2
ld a,(bc) ;swap (bc),(de)
ld h,a
ld a,(de)
ld (bc),a
ld a,h
ld (de),a
pop hl ;restore pivot
jp fleft
next2: pop hl ;restore pivot
pop hl ;pop lo
push bc ;stack=left-hi
ld b,h
ld c,l ;bc=lo,de=right
jp qsloop
;
; >>> end Quicksort <<<
;
I hope some z80 junkies enjoy. And discuss.
-
I am sure I would enjoy this if I knew any z80. I'm actually doing the same thing in my Java class. Nice. :)
-
My only concern at a glance is how it keeps popping without pushing.
-
I am sure I would enjoy this if I knew any z80. I'm actually doing the same thing in my Java class. Nice. :)
For curiosity I read about most used sorting algorithms even before classes, but now I will probably have to do it for class. So yes, it is quite fun to see quicksort in z80.
My only concern at a glance is how it keeps popping without pushing.
It uses the stack to save the elements.
A stack overflow can happen in large lists and maybe cause a slow down because it pushes and then pops a lot. But stack is efficient enough to be even used for clearing large portions of memory when speed is a must.
-
Hmm what stuff does it sort in particular? Or is it an all-purpose sorting routine?
-
Hmm what stuff does it sort in particular? Or is it an all-purpose sorting routine?
It sorts a list of 1 byte numbers only from the least to the greatest.
The author made just because of the challenge and "beauty" for z80 code. It is quicksort (a great algorithm by the way) in old z80.
It is not general purpose.
For curiosity a general purpose would use a passed subroutine (callback it) that compares 2 elements and tells if they are in correct order or not and specify the length of each element.
Talking of sorting algorithms, I know a implementation of heap sort (sigma's code, the author of z80 in 28 days) but it is not as small as this quicksort one.
Sigma's code is for much more generic use unlike this one that sorts 1 byte numbers only from the least to the greatest. Here it is the link (http://www.ticalc.org/archives/files/fileinfo/385/38588.html).
Heap sort is the competitor of quicksort for generic sorting algorithms.
Plus I remember this topic (http://www.junemann.nl/maxcoderz/viewtopic.php?f=8&t=919) in MC forums where the smallest z80 sorting routine is a kind of bubblesort.
So this topic is now a complete reference of z80 sorting code. :D
I shall update WikiTI as well sometime in the future.
-
My only concern at a glance is how it keeps popping without pushing.
that is what the 'ret z' is for, to prevent a pop when the bottom/end of the stack is reached...
-
Oooooooh. I get it now. That makes more sense. I didn't ever think of that... I had only glanced at it before, but now it makes more sense. I like that code...
-
That took me forever to decipher, and I still haven't completely got it. :P oh well, fluentness will come with time... Hopefully. ;)
-
i'm sorry, but i can't resist posting a quicksort program in haskell:
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort [ a | a <- xs, a <= x] ++ [x] ++ quicksort [ a | a <- xs, a > x]
this is really cool to see it implemented in ASM, though
-
O.o. wow, Haskell is........short?
-
O.o. wow, Haskell is........short?
haha, it's a "Very High Level Language". and it has no iterative structures (aka, no for/while/repeat loops). just recursion. the first line of that code says "this function takes a list of any type that can be ordered, and returns a list of the same type"
the second line says "if the input is an empty list, return an empty list"
the third line says "with the inputted list, call quicksort with the lower half of the list as an argument, append the element being being compared against to that quicksortted call, and then call quicksort for the higher half of the list, and append that to the end."
i know.. the last line's confusing.
-
So....it basically does all the work for you?
-
pretty much. recursion is confusing, but it produces short code. quicksort using for and while loops is not so eloquent.
-
OK. I looked it up on wikipedia. "lazy language" lol.
-
haha yeah, it's really confusing at first but i'm beginning to grasp it. here (http://learnyouahaskell.com/) is a good tutorial about it. it's also pretty funny.
-
pretty much. recursion is confusing, but it produces short code. quicksort using for and while loops is not so eloquent.
Recursion can be very nice... but it also can be very memory hungry. ;)
-
pretty much. recursion is confusing, but it produces short code. quicksort using for and while loops is not so eloquent.
Recursion can be very nice... but it also can be very memory hungry. ;)
memory's cheap ;)
-
pretty much. recursion is confusing, but it produces short code. quicksort using for and while loops is not so eloquent.
Recursion can be very nice... but it also can be very memory hungry. ;)
memory's cheap ;)
Not on a calc! ;)
-
pretty much. recursion is confusing, but it produces short code. quicksort using for and while loops is not so eloquent.
Recursion can be very nice... but it also can be very memory hungry. ;)
memory's cheap ;)
Not on a calc! ;)
well, i think we can settle this with the familiar statement: Blame TI
-
Very nice! This routine has been in KnightOS for about 4 months now.
-
Hmm what stuff does it sort in particular? Or is it an all-purpose sorting routine?
It sorts a list of 1 byte numbers only from the least to the greatest.
The author made just because of the challenge and "beauty" for z80 code. It is quicksort (a great algorithm by the way) in old z80.
It is not general purpose.
For curiosity a general purpose would use a passed subroutine (callback it) that compares 2 elements and tells if they are in correct order or not and specify the length of each element.
Ah ok, I was more wondering if such routine was useable to sort, for example, a list of items in a RPG.
-
it may not be general purpose but it sure can sort a crapload of things fast ^^ very well made!
-
Languages that are recursion heavy tend to implement something known as tail call elimination and other techniques that eliminate the excess memory consumption of recursion.
-
I am not sure if I posted already but here are the links to programs that sort in ticalc:
Ubiquitous Z80 QuickSort Implementation (this comes with an example for TI-86)
http://www.ticalc.org/archives/files/fileinfo/347/34716.html
HeapSort for the Z80
http://www.ticalc.org/archives/files/fileinfo/385/38588.html
-
So....it basically does all the work for you?
Yep - and that is the problem. Compiler writes the program for you so often you have only very vague idea about what the program actually does. Worse: sometimes your ideas and compiler ideas differ - and while Haskel gurantees that the produced result will be correct it does not guarantee that the algorithm implemented will be equal to your imagination (because it has no idea about your thought process, you know).
The end result is two-step:
First step: Euphoria. You write 1'000 lines of code, it works (and does the computations which require 10'000 lines of code in more traditional language), everyone is happy.
Second step: Disillusionment. You change some small definition... and everything blows up: instead of producing the result in seconds and using 100MB of RAM (where traditional language will use 10MB) it chews 10GB or RAM and works for a few hours. At this stage you have three choices:
1. Spend few weeks trying to pull the execution model from haskel compiler (to compare it with the model produced by your imagination).
2. Spend month or two rewriting everything in C++ or Java (where you actually control the execution).
3. Give up and just wait till the program will produce something (quite acceptable approach if you only need to run the program once or twice).
Haskell is quite nice for prototyping, but to write robust production systems using it you need years of practice. Few people reach this stage (I'm not among them).