Question about the 'Sort that array'

Moderator: MaxCoderz Staff

User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

leofox wrote:can i make one in basic? Without using the list sort functions of course.
No.
Image
leofox
Calc Master
Posts: 1064
Joined: Fri 17 Dec, 2004 3:22 pm
Location: Probably playing DDR
Contact:

Post by leofox »

ah whatever, i'll make 1 anyway :P .

But i will not bother you with it.
Image
Image
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 »

Is your algo also a stupid sort? I saw CoBB made one.
Nah, mine runs thourgh the array checking every possible key swaps them into proper place. Since there aren't many keys (there is only a max 255) it's more efficient if the array is quite large, so I guess its more like n*k.

I'm gonna try a fast heapsort, I don't know how quicksort could work on calc without using extra memory.
Image
sigma
New Member
Posts: 27
Joined: Thu 31 Mar, 2005 10:56 pm
Location: Stuck in 8-bit land.

Post by sigma »

Jim e wrote:Nah, mine runs thourgh the array checking every possible key swaps them into proper place. Since there aren't many keys (there is only a max 255) it's more efficient if the array is quite large, so I guess its more like n*k.
Same general idea I had, only I wanted to win the prize for "Most Grotesque Abuse of the Stack". :-)
http://sigma.unitedti.org/ -- Really cool content... when I get around to uploading it.
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

On quicksort: All that is sent for every recursion is 'left' and 'right', push them, call, extract. Also, don't use quicksort only *big hint* Now that's enough from me :)
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

Why would you recurse for the right part? You could just jump back to the beginning of the routine, thanks to quicksort being tail recursive on the second call.
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

That's a nice little shortcut :) I usually never get into these when I explain things. First, I think best when I code and second, I want others to think a little too :wink:
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 »

Hey. it's the 26th. So what does CoBB win? 84+se, $10000, new car, what? :lol:
Image
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Post by Timendus »

..is it over..? Why hasn't a winner been declared or anything..?
I've been on vacation, and I see I missed this entire thing. Too bad, I just passed the algorithms and complexity class, and would have liked to join the contest :) (Not that there's any point to that anymore :P)
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

Well,

we have a winner. Congrats to CoBB! 15 Bytes is a real achievement! Thanks to all entries, you guys did a great job.

I'm closing this thread now.

Greetings,
kv83

P.s.: sorry for that late reaction
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 »

No speed winner? :cry: I tried my best! Congratulations Cobb!
"They say that sea was created by a man named Maarten Zwartbol, a long time ago...." - Duck, an old Corbin version
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

I have no clue how to calculate the speed accurate... Nor do I have enough time to do that.
Image
threefingeredguy
Calc King
Posts: 2195
Joined: Sun 27 Mar, 2005 4:06 am
Location: sleeping
Contact:

Post by threefingeredguy »

Just get a table that says the clock spped of each asm function and add them up.
Image
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

threefingeredguy wrote:Just get a table that says the clock spped of each asm function and add them up.
As simple as that may sound, it isn't. How do you compare the functions in speed of sorting a array? A routine heavinly depends on the array when it comes to speed. One routine may sort a half-sorted array faster than almost-sorted array, and the other routine sorts a almost-sorted array faster than the half-sorted... you see what I mean?
Image
threefingeredguy
Calc King
Posts: 2195
Joined: Sun 27 Mar, 2005 4:06 am
Location: sleeping
Contact:

Post by threefingeredguy »

Ah yes, my method would only work when they are all sorting the same type of sort the same number of times. My apologies. Is the interrupt frequency constant, because then you could use that. Or you could test them on an 84+ and read in the current clock time, then run the program, then read in the cloc time at the end.
Image
Post Reply