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

0 Members and 1 Guest are viewing this topic.

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #15 on: November 13, 2010, 09:19:29 pm »
haha yeah, it's really confusing at first but i'm beginning to grasp it. here is a good tutorial about it. it's also pretty funny.


Offline Ranman

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1354
  • Rating: +83/-0
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #16 on: November 13, 2010, 09:39:37 pm »
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. ;)
Ranman
Bringing Randy Glover's Jumpman to the TI-89 calculator. Download available at Ticalc.

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #17 on: November 13, 2010, 09:43:35 pm »
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 ;)


Offline Ranman

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1354
  • Rating: +83/-0
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #18 on: November 13, 2010, 09:59:58 pm »
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! ;)
« Last Edit: November 13, 2010, 10:00:31 pm by Ranman »
Ranman
Bringing Randy Glover's Jumpman to the TI-89 calculator. Download available at Ticalc.

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #19 on: November 13, 2010, 10:03:06 pm »
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


SirCmpwn

  • Guest
Re: Quicksort in z80 (note: not by me)
« Reply #20 on: November 13, 2010, 10:06:17 pm »
Very nice!  This routine has been in KnightOS for about 4 months now.

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 #21 on: November 14, 2010, 12:36:44 am »
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.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #22 on: November 14, 2010, 12:47:45 am »
it may not be general purpose but it sure can sort a crapload of things fast ^^ very well made!

Offline DrDnar

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 546
  • Rating: +97/-1
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #23 on: November 14, 2010, 02:32:36 am »
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.
"No tools will make a man a skilled workman, or master of defense, nor be of any use to him who has not learned how to handle them, and has never bestowed any attention upon them. . . . Yes, [] the tools which would teach men their own use would be beyond price."—Plato's The Republic, circa 380 BC

Offline Galandros

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1140
  • Rating: +42/-10
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #24 on: November 15, 2010, 03:57:02 pm »
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
« Last Edit: November 15, 2010, 03:57:30 pm by Galandros »
Hobbing in calculator projects.

Offline calcforth

  • LV3 Member (Next: 100)
  • ***
  • Posts: 62
  • Rating: +4/-4
    • View Profile
Re: Quicksort in z80 (note: not by me)
« Reply #25 on: November 15, 2010, 04:35:54 pm »
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).