So you think you can code ... :-) How fast can you sort ???

gtoal

If you pride yourself on being a slick coder, try writing a sort program that's faster than the best of these…

http://scratch.mit.edu/projects/43755392/

Use regular Scratch, no hacks. I'll add people's entries to the project above.

This is partly a bit of fun but the underlying goal is to iterate towards the fastest sorting implementation possible on Scratch. (So don't hard-code things like the array size or name for example - it should be a general-purpose sort with a lower and upper bound parameter.)

Don't try to optimize for small arrays - they'll be sorted fast enough anyway. We want something that performs well on large arrays - at least 10,000 elements and above.

Graham

Thepuzzlegame

Hmm, looks interesting!

MegaApuTurkUltra

I challenge someone to make a sort faster than mine :)

__init__

This went faster than I could screenshot, but once MegaApu's time was 1337 milliseconds.

MathWizz

I made a heapsort last night that is about 33% slower than MATU's. I just realized that it would be really easy to make in place though, so I think it has a chance at beating MATU's quicksort yet.

Zro716

now this makes me think, what's the most inefficient way to sort? hmm….

djdolphin

Zro716 wrote:
now this makes me think, what's the most inefficient way to sort? hmm….

This?

MegaApuTurkUltra

djdolphin wrote:
Zro716 wrote:
now this makes me think, what's the most inefficient way to sort? hmm….
This?

Lol so fast right?

Hardmath123

Zro716 wrote:
now this makes me think, what's the most inefficient way to sort? hmm….

Man, am I a genius. Check out this sorting algorithm I just invented.

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait
example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

Not cited because source is not exactly Scratch-appropriate.

gtoal

MathWizz wrote:
I made a heapsort last night that is about 33% slower than MATU's. I just realized that it would be really easy to make in place though, so I think it has a chance at beating MATU's quicksort yet.

Well, I just squeezed between 5 and 10% more out of MegaApuTurkUltra's quicksort by two modifications:

1) convert final recursive call into a loop back to the start
2) choose which partition to recurse on and which to loop on according to the size of the partition. If it is unbalanced, recurse on the smaller one.

G

MegaApuTurkUltra

gtoal wrote:
MathWizz wrote:
I made a heapsort last night that is about 33% slower than MATU's. I just realized that it would be really easy to make in place though, so I think it has a chance at beating MATU's quicksort yet.

Well, I just squeezed between 5 and 10% more out of MegaApuTurkUltra's quicksort by two modifications:

1) convert final recursive call into a loop back to the start
2) choose which partition to recurse on and which to loop on according to the size of the partition. If it is unbalanced, recurse on the smaller one.

G

Cool, thanks!

gtoal

MegaApuTurkUltra wrote:
gtoal wrote:
MathWizz wrote:
I made a heapsort last night that is about 33% slower than MATU's. I just realized that it would be really easy to make in place though, so I think it has a chance at beating MATU's quicksort yet.

Well, I just squeezed between 5 and 10% more out of MegaApuTurkUltra's quicksort by two modifications:

1) convert final recursive call into a loop back to the start
2) choose which partition to recurse on and which to loop on according to the size of the partition. If it is unbalanced, recurse on the smaller one.

G
Cool, thanks!

It'll give more of a win on partially sorted data where the partitions are unbalanced. In the average case it'll be about the same as your original.

I know of some other tweaks but I think now the area to explore is in taking advantage of some of Scratch's implementation details. Also I need to modify the test harness to check some extreme cases so that we converge on an algorithm with no extreme worst-case performance.

One trick I like is randomizing the array before sorting. It doesn't let you take advantage of partially sorted data but it also protects against worst-case performance for partially sorted data.

G

TheLogFather

I've been keeping an eye on this to see how it goes. I have an idea for a bit of a different algorithm that might be competitive, so I'll give it a go at some point soon… (might fail badly, of course!)

On a slightly different note, I have been talking a bit with gtoal about some slight questions over whether this is exactly what we want to optimise - or at least if it might be missing something that's important to include, in order to pit it against methods that only return a sort *index* list (rather than actually returning a sorted list).

Here's the link to the comments: http://scratch.mit.edu/users/DadOfMrLog/#comments-6952602

Thoughts…?

gtoal

TheLogFather wrote:
I've been keeping an eye on this to see how it goes. I have an idea for a bit of a different algorithm that might be competitive, so I'll give it a go at some point soon… (might fail badly, of course!)

On a slightly different note, I have been talking a bit with gtoal about some slight questions over whether this is exactly what we want to optimise - or at least if it might be missing something that's important to include, in order to pit it against methods that only return a sort *index* list (rather than actually returning a sorted list).

Here's the link to the comments: http://scratch.mit.edu/users/DadOfMrLog/#comments-6952602

Thoughts…?

I agree. I see the outcome of this effort being a wiki entry that points to maybe two or three projects that implement the best sort algorithm for specific purposes, and maybe one simple and general one for people that don't have the time to research the idiosyncrasies of their data.

There are many factors to take into account, for example does it perform well when most of the keys are identical? Or mostly sorted, whether ascending or descending? Can you afford the space for a second copy of the array if it is not a sort-in-place algorithm, or it is a sort-in-place but you don't want to overwrite the original data? What if you acquire the data serially? Or know it is restricted in range? Or only ever contains numbers but not text strings? Do you care if it has a high start-up overhead which penalizes sorting small lists but pays off with huge ones?

Despite the competition for the ‘best’ sorting algorithm, there actually is no best because it depends on the application. But there can be code that is ‘not worst’ - which never performs really badly regardless of the inputs.

Anyway, don't everyone get too hung up in worrying about winning the competition. It's just an excuse to have some fun and to help improve an area of Scratch coding that I've noticed coming up a few times lately, especially with more people trying fairly advanced 3D engines nowadays that require depth sorting.

By the way, I need to go on a trip next week and I may be gone a little time. Zro716 will take over the testing and judging. I'll drop in when I can but I don't think I can be a regular contributor for a few months.

regards

Graham

TheLogFather

TheLogFather wrote:
I've been keeping an eye on this to see how it goes. I have an idea for a bit of a different algorithm that might be competitive, so I'll give it a go at some point soon… (might fail badly, of course!)

I've started work on this tonight, so I expect I'll have something to show for it some time tomorrow…

Not sure how much it'll shave off the best time so far, but I'm hopeful it'll beat it by 10% or more…

novice27b

Here's my entry: http://scratch.mit.edu/projects/44854750

It's an implementation of a Counting Sort. It takes about 600ms on my slow laptop, so I think it may be the fastest in this thread so far! I made use of the fact that replacing list elements is relatively fast in scratch. The only downside is memory usage, proportional to the range of input values.

Could someone else please verify my time, and possibly add it to the “shootout” project?

Last edited by novice27b (Jan. 25, 2015 20:03:46)

Firedrake969

You may want to give the link to the project, not this topic…

I got 257 ms (although repeatedly sorting does increase time needed)

Last edited by Firedrake969 (Jan. 25, 2015 19:57:41)

novice27b

Firedrake969 wrote:
You may want to give the link to the project, not this topic…

I got 257 ms (although repeatedly sorting does increase time needed)

Thanks, I fixed the link. What do you mean by repeated sorting?

Firedrake969

novice27b wrote:
Firedrake969 wrote:
You may want to give the link to the project, not this topic…

I got 257 ms (although repeatedly sorting does increase time needed)

Thanks, I fixed the link. What do you mean by repeated sorting?

Hitting space after the sort finishes, and doing that a few times

novice27b

Firedrake969 wrote:
novice27b wrote:
Firedrake969 wrote:
You may want to give the link to the project, not this topic…

I got 257 ms (although repeatedly sorting does increase time needed)

Thanks, I fixed the link. What do you mean by repeated sorting?
Hitting space after the sort finishes, and doing that a few times

Ah, I fixed that by re-initialising the count list each time. Unfortunately, that has increased the sort time from 600ms to 1000ms.

Discuss Scratch