Question about the 'Sort that array'
Moderator: MaxCoderz Staff
- Jim e
- Calc King
- Posts: 2457
- Joined: Sun 26 Dec, 2004 5:27 am
- Location: SXIOPO = Infinite lives for both players
- Contact:
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.
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.
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.
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.
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
Insert this somewhere there ->
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
Insert this somewhere there ->
-
- Maxcoderz Staff
- Posts: 791
- Joined: Fri 17 Dec, 2004 5:33 pm
- Location: On the dark side of the moon.
- Contact:
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.
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
- Jim e
- Calc King
- Posts: 2457
- Joined: Sun 26 Dec, 2004 5:27 am
- Location: SXIOPO = Infinite lives for both players
- Contact:
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*
Edit: Just saw cobbs code, I am such a failure. My code appears bloated & slow now. *tips hat*
Last edited by Jim e on Sat 02 Jul, 2005 8:30 am, edited 2 times in total.
-
- MCF Legend
- Posts: 1601
- Joined: Mon 20 Dec, 2004 8:45 am
- Location: Budapest, Absurdistan
- Contact:
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?
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?