MaxCoderz

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.

What do you mean?

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.

OK now i get you, you dont have to know the contents but it helps.

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

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

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 ->

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.

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.

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.

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.

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*

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).

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

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?

I take that back i think it might cause problems.