« previous next »
Pages: [1] 2   Go Down

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

0 Members and 1 Guest are viewing this topic.

Offline Galandros

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1140
  • Rating: +42/-10
    • View Profile
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.
Logged
Hobbing in calculator projects.

Offline MRide

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 711
  • Rating: +14/-0
  • You can't see this.
    • View Profile
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. :)
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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.
Logged

Offline Galandros

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1140
  • Rating: +42/-10
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #3 on: November 13, 2010, 01:41:00 pm »
Quote from: MRide 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. :)
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.

Quote from: Xeda112358 on November 13, 2010, 11:14:03 am
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 »
Logged
Hobbing in calculator projects.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
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?
Logged

Offline Galandros

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1140
  • Rating: +42/-10
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #5 on: November 13, 2010, 01:54:00 pm »
Quote from: DJ Omnimaga on November 13, 2010, 01:43:28 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. :D
I shall update WikiTI as well sometime in the future.
« Last Edit: November 13, 2010, 01:56:05 pm by Galandros »
Logged
Hobbing in calculator projects.

Offline matthias1992

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 408
  • Rating: +33/-5
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #6 on: November 13, 2010, 01:58:50 pm »
Quote from: Xeda112358 on November 13, 2010, 11:14:03 am
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...
Logged
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-

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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...
Logged

Offline 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.
    • View Profile
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.  :P  oh well, fluentness will come with time... Hopefully.  ;)
Logged

Spoiler For =====My Projects=====:
Minor setback due to code messing up.  On hold for Contest.
<hr>
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>

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
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
Logged

Offline MRide

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

Offline nemo

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

Offline MRide

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 711
  • Rating: +14/-0
  • You can't see this.
    • View Profile
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?
Logged

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
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.
Logged

Offline MRide

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 711
  • Rating: +14/-0
  • You can't see this.
    • View Profile
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.
Logged
Pages: [1] 2   Go Up
« previous next »