MaxCoderz

for your 1 bit pleasure!

All times are UTC




Post new topic Reply to topic  [ 70 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next
Author Message
 Post subject:
PostPosted: Fri 01 Jul, 2005 7:35 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 4095
Location: I cant seem to get out of this cryogenic chamber!
The only problem i have with Jim e's routine is that it appears that you already know the contents of the array before even assembling ... which kind of defeats the purpose of having a sort routine as you would just sort it by hand before assembling.

_________________
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Fri 01 Jul, 2005 7:46 pm 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
What do you mean?

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Fri 01 Jul, 2005 8:00 pm 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
Knowing the contents?? Sort by hand?? I thought we were assuming it was random and variable in size.

You only have to know the stop indicator, thats it(even you require that). If the entire contents could contain any one byte number(minus the stop) than make C equal 0. If you know 0 isn't in there than just skip it, you don't have to skip it but it's faster if you do.

In this case bubble sort is faster, mine makes 255 passes over the number of elements in the array, even if it is already sorted. But I wasn't optimizing for speed. :roll:

I tried to make a small bubble sort but I had to "cheat" and it required 22 bytes. Not cheating 24bytes, that wasn't good enough.

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Fri 01 Jul, 2005 8:13 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 4095
Location: I cant seem to get out of this cryogenic chamber!
OK now i get you, you dont have to know the contents but it helps.

Your comments in your entry post ..... lol.

_________________
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Fri 01 Jul, 2005 11:40 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Wed 15 Dec, 2004 7:26 pm
Posts: 2735
Location: The Hague, Netherlands
CoBB wrote:
Weighing: announce a speed winner and a size winner. It would be rather hard to beat you in the latter category. :)
Good point lets do that :)

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 12:02 am 
Offline
Calc Wizard

Joined: Sun 19 Dec, 2004 9:02 pm
Posts: 585
Location: Sweden
Quick-sort without any extra storage? I wonder how one should save the recursion information :p
As for the set of arrays to be sorted, just check out a few sort algorithms and see what they are good/bad at and try all cases, I mentioned a few cases in my last post to start with.
Another question: now that there is performance in this contest too, is it valid to reserve like a 376-bytes big buffer by code? 376 'nop's for a buffer (hope the number of 'nop's will fool most leechers...), could be considered smc :)

And sorry if my post turned out a little harsh, man I didn't even use a smiley :oops:
Insert this somewhere there -> :D


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 5:03 am 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
coelurus wrote:
Quick-sort without any extra storage? I wonder how one should save the recursion information :p

Using the stack is allowed. On the other hand, as I understand the rules, fiddling with sp isn't. ;)

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 6:10 am 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
Theres only 400 bytes on the stack. How many times would a quicksort routine have to recurse itself, am I right in assuming log2(n) at the most?

Well if theres a speed contest then I'd like to submit a second entry later, mines kinda slow. :oops: :roll:

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 7:05 am 
Offline
Maxcoderz Staff

Joined: Fri 17 Dec, 2004 5:33 pm
Posts: 790
Location: On the dark side of the moon.
Defining a size winner is kind of tricky.

What if I made a Bogosort? According to wikipedia:
one example of which is attempting to sort a deck of cards by repeatedly throwing the deck in the air, picking the cards up at random, and then testing whether the cards are in sorted order.

Quite small but awfully slow.

_________________
"They say that sea was created by a man named Maarten Zwartbol, a long time ago...." - Duck, an old Corbin version


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 7:10 am 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
Jim e wrote:
How many times would a quicksort routine have to recurse itself, am I right in assuming log2(n) at the most?

No, it isn't guaranteed to recurse less than n times, but logn is typical.

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 8:16 am 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
Oh i see now, if eveything in the array was the same it would recurse n times, right? That could be a problem.

Edit: Just saw cobbs code, I am such a failure. My code appears bloated & slow now. *tips hat* :worship:

_________________
Image


Last edited by Jim e on Sat 02 Jul, 2005 8:30 am, edited 2 times in total.

Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 8:29 am 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
Slow? No, my code uses O(n^3) time. That's hideous, gently put. :) It's basically a bubble sort where the swap is also O(n) instead of O(1).

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 8:32 am 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
Yeah but mine makes 255 passes no matter what. In practice i think mine is slower.

One more thing, if you make a slight change you could sort an array that is only the stop indicator. But i don't want to give it away. hehe :wink:

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 8:58 am 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
Well, at first glance I see two possibilities:

1. Moving cp c \ ret z a bit higher, so the first element is also checked. However, that would also mean that the array couldn't contain elements greater than the terminator at the very end. As long as the terminator is $ff, that's okay, but in that case passing it as a parameter is cheating, since no other value guarantees correct behaviour (the last element can be sorted after the terminator).
2. Changing the first ld a,(hl) to xor a, and setting de to one byte before the array. That doesn't introduce the previous problem, but it's also an ugly interface.

Not being able to sort empty arrays seems to be the least bad among these. Or you had something else in mind?

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 02 Jul, 2005 9:07 am 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
I take that back i think it might cause problems.

_________________
Image


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 70 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB ® Forum Software © phpBB Group | DVGFX2 by: Matt