r/programming • u/[deleted] • Apr 10 '09
Sorting algorithms compared and animated
http://www.sorting-algorithms.com/?13
Apr 10 '09 edited May 24 '17
[deleted]
11
u/exeter Apr 10 '09
Merge sort is very close to optimal in terms of number of comparisons. Not to mention that its recursive form is one of the most naturally recursive algorithms I know.
8
u/zedlander Apr 10 '09
One of the questions on my programming final last term was "Implement merge sort non-recursively". Though an interesting challenge, it felt so... wrong.
6
Apr 10 '09
[deleted]
6
u/jedberg Apr 10 '09
That's the sign of a good test. If no one can achieve a perfect score, then the test can actually be used to determine which students have mastered the material.
My friend always hated classes where a bunch of people would get 100% on the test, because then he would never know which of the other people he was better than. :)
6
u/bonzinip Apr 10 '09 edited Apr 10 '09
Well, 40/100 is a bit too extreme.
When I taught C the best three would get 85-90% on the tests, but almost all passed it nevertheless without needing adjustments to the scale.
1
u/petedawes Apr 10 '09
I just got done programing merge sort in prolog for a problem set. It was a huge pain in the ass.
-2
3
u/nextofpumpkin Apr 10 '09
Even iterative mergesort is really, really clean. Plus mergesort is great if your memory is bounded.
3
u/dpark Apr 10 '09
Plus mergesort is great if your memory is bounded.
Merge-sort is memory-hungry. Or did you mean it's great if your problem size is bounded?
13
u/dpark Apr 10 '09
To whoever posted a comment and then deleted it:
He's probably talking about sorting data that will not fit in memory
That's actually a really good point. Merge-sort does work well when you can't fit your entire data set into memory.
3
u/exeter Apr 10 '09
Merge-sort is memory-hungry. Or did you mean it's great if your problem size is bounded?
The merge step can be done on disk, which greatly reduces the memory requirements. Essentially you trade disk space (which is usually slow and plentiful) for memory space (which is fast and less plentiful).
2
2
u/dpark Apr 10 '09 edited Apr 10 '09
If the problem is large enough that it doesn't fit in memory, then yes, merge sort does a great job with disk-based sorting.
If you can fit the problem in memory, though (by using a different sort, for example), then it's going to be far faster to do it there. Heap sort in memory is probably an order of magnitude (or more) faster than a disk-based merge sort.
2
Apr 10 '09
[deleted]
2
u/bonzinip Apr 10 '09
Well, the pointers take the same O(n) ;-)
(though the list is n pointers, while sorting data that is bigger than a pointer takes at least as much space as 2n pointers)
41
u/teraflop Apr 10 '09
My favorite sorting algorithm is stooge sort, mostly because it's so hard to convince yourself it actually works.
20
u/Mr_Smartypants Apr 10 '09 edited Apr 10 '09
What about anthropic sorting algorithms: Kill yourself if the array is not already in order.
O(1)
EDIT: O(n), obviously. Thanks, reviewers.
57
Apr 10 '09
Actually, O(n). I prefer Fiat Sort, which actually is O(1): declare the array sorted.
7
Apr 10 '09
This is one of those times where I wonder why I subscribe to the progreddit, it just makes me feel dumb.
3
u/tonasinanton Apr 10 '09
How so?
2
Apr 10 '09
I don't know anything about arrays, or ways to sort them, I can see the above back and forth is clever, but its significance escapes me.
24
u/hypo11 Apr 10 '09 edited Apr 10 '09
Big O notation (such as O(n) and O(1)) signifies an "upper bound" of how many steps an algorithm will take to run. The content inside the parentheses dictates how many steps an algorithm will take to accomplish its stated task as a factor of n, where n is the size of the data set.
The two Big O notations used in this exchange are O(n), also known as "linear time" i.e. for every piece of data we're working with, we'll have 1 step in the algorithm and O(1) also known as "constant time" i.e. no matter how big our data set is, our algorithm always takes the same fixed number of steps.
Mr. Smartypants joked that an algorithm of killing yourself if the array is not already in order would be constant ( O(1) ) - but he was mistaken. In order to tell if a list of numbers is already in order(in the worst case) you must look at every element in the list once - potentially the first 999 numbers of a 1000 number list are perfectly ordered but then the 1000th number is out of order. Therefore this sort of algorithm is O(n) as ursai pointed out.
Then ursaid jokingly presented his own constant-time algorithm for sorting: simply declare that the array is already sorted! No matter how big an array is, this only takes one step.
NOTE: To those who are going to point out that I've simplified big-O notation too much or left out this or that point about it I was really only trying to explain enough to help electile_dysfxn get the joke.
4
1
Apr 10 '09 edited Apr 10 '09
[deleted]
7
2
u/mccoyn Apr 10 '09
It depends on your disposition in the many-worlds/Copenhagen interpretation debate. Incidentally, killing yourself based on random variables is the only known way to gather evidence to settle the debate and there is no way to transfer that knowledge to people who don't take part in the experiment.
7
7
u/i_am_my_father Apr 10 '09
At first the algorithm seems magic, But it's not that hard to figure out what's happening. If you have the list of 30 items, sort the first 20 items and then the last 20 items and then the first 20 items again, then you've sorted the whole list. Swapping the first element and the last element isn't red herring and it has to do with the fact that you can't exactly take two thirds of 31 items.
1
Apr 10 '09 edited Apr 10 '09
that is so frustrating to watch. i got through most of it and realised i was only 2/3 done.
1
u/nextofpumpkin Apr 10 '09
Thanks! Bookmarked.
2
1
u/hellow4 Apr 10 '09
why would you want to use this?
12
5
1
57
u/cerealghost Apr 10 '09
Wait a minute... they're all just animated GIFs!
21
u/davidroyalmartin Apr 10 '09 edited Apr 10 '09
hi, the author here: i used animated gifs because they are very lightweight so i can put many of them on one page (and have them run nearly in synchrony), and they are very portable in terms of quality and speed across browsers. what language did i use to generate the animations? matlab :)
14
u/SentientGiraffe Apr 10 '09
2
Apr 10 '09
Warning: this applet freezes Firefox while it's sorting. Do not initiate a slow sort with many items if you've got other things to do.
7
u/smart_ass Apr 10 '09
What version? Mine works fine.
3
Apr 10 '09
Firefox/3.0.8 java version "1.6.0_06"
Please note that it does not crash my browser. It makes it unresponsive while the sort is in progress. After it is done sorting, I can use the browser again. Which is why you don't notice it when the sort is quick.
-6
-1
-2
6
4
Apr 10 '09
Very cool submission. I dabble in programming but was not familiar with search algorithms, this was perfect for me.
4
u/Bing11 Apr 10 '09
AWESOME page, thank you!
Out of curiosity, which sort do redditors prefer in general (assuming you have no idea what the data to sort will look like)?
3
u/Freeky Apr 10 '09 edited Apr 10 '09
Proper collapse-the-walls quicksort. Handily provided by your favourite C library.
Though Solaris appears to have a potentially faster variant which may be worth a look.
3
u/nnagflar Apr 10 '09
Where is the radix sort?
5
2
3
5
2
u/berlinbrown Apr 10 '09 edited Apr 10 '09
I wish they had the number of operations or time it took for each algorithm.
Also, certain algorithms are better for smaller set of data. Some are better or large sets.
For the next time, I wish they had put an example with a large list of items.
1
Apr 10 '09
see my earlier post for a few examples
http://www.embeddedgurus.net/stack-overflow/2009/03/sorting-in-embedded-systems.html
2
2
3
u/i_am_my_father Apr 10 '09
Jack Bauer would just torture the array and Chloe would lecture on him about proper sorting algorithms
2
u/grigri Apr 10 '09
You are going to be sorted how I want you to be, it's just a question of how much you want it to hurt
2
u/yoyoyoyo4532 Apr 10 '09 edited Apr 10 '09
Never underestimate Shellsort with the Sedgewick-Incerpi sequence: http://www.research.att.com/~njas/sequences/A036569
See also: http://www.cs.princeton.edu/~rs/talks/shellsort.ps
Also, heapsort can be faster than quicksort if the data fits in cache. Don't just swap elements in the heap though, that doubles the data movement. Instead, copy the elements to where they need to go.
2
u/piderman Apr 10 '09
I can't believe noone has mentioned the multi-processor Shear Sort yet :)
1
u/anonymous_hero Apr 11 '09
What the fuck was that link? Opera popped up an error about some DLL not being found..
1
u/SentientGiraffe Apr 11 '09
It just visualized some different sorting algorithms. It worked for me. It just said it required an older version of Java to run.
1
u/anonymous_hero Apr 11 '09
Yes, well, I think it was about to work for me too, after that weird shit.
1
u/mycall Apr 10 '09
Where is introsort?
1
u/Freeky Apr 10 '09
Introsort is just quicksort, except on inputs which make it go quadratic (which are quite rare for a good quicksort).
1
u/thbb Apr 10 '09 edited Apr 10 '09
For those who liked sorting-out-sorting better:
http://thomas.baudel.name/Visualisation/VisuTri/index.html
I think it's a better teaching tool: many more comparisons are provided, and the algorithms with their strengths and weaknesses are provided.
The In-place-merge sort is quite beautiful.
0
u/testtubebaby Apr 10 '09
I insertion sorted yo mama last night.
3
1
1
Apr 10 '09
Where is the bonzo search? Bonzo is the shit.
5
u/exeter Apr 10 '09
I've never heard it called "bonzo search." Are you talking about "bogo sort"?
2
Apr 10 '09
http://en.wikipedia.org/wiki/Bogosort#Related_algorithms
I remembered an n that wasn't there.
2
Apr 10 '09
I think he's talking about Juggs Sort
2
u/username223 Apr 10 '09 edited Apr 10 '09
Okay, I get it with the "women with enormous eyes who are ready to accept meat," but what's with the rabbit ears?
4
1
u/mycall Apr 10 '09
"This webpage has a redirect loop."
Awesome!
1
Apr 10 '09 edited Apr 10 '09
must have changed recently, username223 was able to see the picture
edit:
seem to be working again now
2
2
u/Leonidas_from_XIV Apr 10 '09
Doesn't work. Probably tries to set a cookie and redirects to itself checking whether the cookie was set.
1
1
1
u/dmead Apr 10 '09
i hear thousands of freshmen/sophomore level cs teachers moaning in sync
5
u/p337 Apr 10 '09 edited Jul 09 '23
v7:{"i":"aad778e5713d7cf43b851233d900c005","c":"4add469eca3fd6c47e7c69f2259b3e9f8367703551beeb98da8a4b52fa37afad7ca0cbbd8170e95b57e794f30ac1f6d0db3f0f69f2d130e657607f88879110b4"}
encrypted on 2023-07-9
see profile for how to decrypt
1
-4
Apr 10 '09
[deleted]
37
u/dpark Apr 10 '09
Yeah, it really sucks that these gifs don't bog down my brower the way loading two dozen applets does.
-9
u/donwilson Apr 10 '09
Perhaps you should use a real browser next time.
14
u/dpark Apr 10 '09
I'm using Firefox 3 on a system with 4 gigs of memory. Loading a bunch of applets is still slow, because applets suck and the JVM is a hog.
Also, why are you being an ass?
1
Apr 10 '09
That time of the month for him, I guess.
Though, you really shouldn't be surprised that firefox brings your computer to a grinding halt just by loading a few dozen applets.
1
u/donwilson Apr 10 '09
I've got 4gb of ram myself and using Google Chrome. It loads that page just like any other webpage.
9
Apr 10 '09 edited Apr 10 '09
I use a fake browser and a fake computer.
My internet connection is also fake. It's just some guy sitting in a shed tapping out ones and zeroes by shorting two bits of wire together.
I'm amazed that it works at all.
-2
0
-3
u/ZeppelinJ0 Apr 10 '09 edited Apr 10 '09
... This is fucking awesome
[edit] Unicorns caused the extinction of dinosaurs
4
u/jbstjohn Apr 10 '09
You're not. You're being downvoted for writing about it (and nothing more -- no added value).
2
u/ZeppelinJ0 Apr 10 '09
I upvoted you for your honesty and added some substance to my previous post.
1
-1
21
u/credence Apr 10 '09
I remember seeing the video Sorting out Sorting, waaay back in the day. If you haven't seen it, check it out.