### Author Topic: Quicksort in z80 (note: not by me)  (Read 11905 times)

0 Members and 1 Guest are viewing this topic.

#### Galandros

• LV9 Veteran (Next: 1337)
• Posts: 1140
• Rating: +42/-10
##### Quicksort in z80 (note: not by me)
« 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.
Hobbing in calculator projects.

#### MRide

• LV8 Addict (Next: 1000)
• Posts: 711
• Rating: +14/-0
• You can't see this.
##### Re: Quicksort in z80 (note: not by me)
« Reply #1 on: November 13, 2010, 11:01:44 am »
I am sure I would enjoy this if I knew any z80.  I'm actually doing the same thing in my Java class. Nice.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4704
• Rating: +719/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Quicksort in z80 (note: not by me)
« Reply #2 on: November 13, 2010, 11:14:03 am »
My only concern at a glance is how it keeps popping without pushing.

#### Galandros

• LV9 Veteran (Next: 1337)
• Posts: 1140
• Rating: +42/-10
##### Re: Quicksort in z80 (note: not by me)
« Reply #3 on: November 13, 2010, 01:41:00 pm »
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.
« Last Edit: November 13, 2010, 01:50:43 pm by Galandros »
Hobbing in calculator projects.

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55937
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### Re: Quicksort in z80 (note: not by me)
« Reply #4 on: November 13, 2010, 01:43:28 pm »
Hmm what stuff does it sort in particular? Or is it an all-purpose sorting routine?
Dream of Omnimaga

#### Galandros

• LV9 Veteran (Next: 1337)
• Posts: 1140
• Rating: +42/-10
##### Re: Quicksort in z80 (note: not by me)
« Reply #5 on: November 13, 2010, 01:54:00 pm »
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.
Heap sort is the competitor of quicksort for generic sorting algorithms.
Plus I remember this topic 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.
I shall update WikiTI as well sometime in the future.
« Last Edit: November 13, 2010, 01:56:05 pm by Galandros »
Hobbing in calculator projects.

#### matthias1992

• LV6 Super Member (Next: 500)
• Posts: 408
• Rating: +33/-5
##### Re: Quicksort in z80 (note: not by me)
« Reply #6 on: November 13, 2010, 01:58:50 pm »
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...
MASM xxxxxxxxxx aborted | SADce ====:::::: 40% -Halted until further notice| XAOS =====::::: 50% -Units done| SKYBOX2D engine ========== 100% -Pre-alpha done. Need to  document it and extend |

~Those who dream by day are cognizant of much more than those who dream by night only. -Sir Edgar Allen Poe-

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4704
• Rating: +719/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Quicksort in z80 (note: not by me)
« Reply #7 on: November 13, 2010, 08:00:31 pm »
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...

#### yunhua98

• You won't this read sentence right.
• LV11 Super Veteran (Next: 3000)
• Posts: 2718
• Rating: +214/-12
• Go take a dive in the River Lethe.
##### Re: Quicksort in z80 (note: not by me)
« Reply #8 on: November 13, 2010, 08:30:51 pm »
That took me forever to decipher, and I still haven't completely got it.    oh well, fluentness will come with time... Hopefully.

 Spoiler For =====My Projects=====: Minor setback due to code messing up.  On hold for Contest.
On hold for Contest. Spoiler For ===Staff Memberships===:
Have you seen any good news-worthy programs/events?  If so, PM me with an article to be included in the next issue of CGPN!
The Game is only a demo, the code that allows one to win hasn't been done.
To paraphrase Oedipus, Hamlet, Lear, and all those guys, "I wish I had known this some time ago."
Signature Last Updated: 12/26/11
<hr>

#### nemo

• LV9 Veteran (Next: 1337)
• Posts: 1203
• Rating: +95/-11
##### Re: Quicksort in z80 (note: not by me)
« Reply #9 on: November 13, 2010, 08:38:53 pm »
i'm sorry, but i can't resist posting a quicksort program in haskell:

Code: [Select]
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

#### MRide

• LV8 Addict (Next: 1000)
• Posts: 711
• Rating: +14/-0
• You can't see this.
##### Re: Quicksort in z80 (note: not by me)
« Reply #10 on: November 13, 2010, 08:43:20 pm »
O.o.  wow, Haskell is........short?

#### nemo

• LV9 Veteran (Next: 1337)
• Posts: 1203
• Rating: +95/-11
##### Re: Quicksort in z80 (note: not by me)
« Reply #11 on: November 13, 2010, 08:47:26 pm »
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.

#### MRide

• LV8 Addict (Next: 1000)
• Posts: 711
• Rating: +14/-0
• You can't see this.
##### Re: Quicksort in z80 (note: not by me)
« Reply #12 on: November 13, 2010, 08:48:54 pm »
So....it basically does all the work for you?

#### nemo

• LV9 Veteran (Next: 1337)
• Posts: 1203
• Rating: +95/-11
##### Re: Quicksort in z80 (note: not by me)
« Reply #13 on: November 13, 2010, 08:53:20 pm »
pretty much. recursion is confusing, but it produces short code. quicksort using for and while loops is not so eloquent.

#### MRide

• LV8 Addict (Next: 1000)
• Posts: 711
• Rating: +14/-0
• You can't see this.
##### Re: Quicksort in z80 (note: not by me)
« Reply #14 on: November 13, 2010, 08:58:39 pm »
OK.  I looked it up on wikipedia. "lazy language" lol.