Question about the 'Sort that array'

Moderator: MaxCoderz Staff

User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4141
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

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
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

What do you mean?
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4141
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

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
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

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
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

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
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

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. ;)
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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
Kozak
Maxcoderz Staff
Posts: 791
Joined: Fri 17 Dec, 2004 5:33 pm
Location: On the dark side of the moon.
Contact:

Post by Kozak »

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
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

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.
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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:
Last edited by Jim e on Sat 02 Jul, 2005 8:30 am, edited 2 times in total.
Image
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

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).
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

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?
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

I take that back i think it might cause problems.
Image
Post Reply