What is Digg?66 Comments
- skotski, on 10/12/2007, -0/+34Perfect! Three minutes is just about the extent of my attention span.
- rootryan, on 10/12/2007, -0/+21mergesort kicks ass. Fun page, for three minutes.
- PatrickFisher, on 10/12/2007, -6/+22Hey, if anyone wants, I can make an animation that demonstrates paint drying.
- dimator, on 10/12/2007, -8/+20More than 10 years after Java was introduced, it still slows down my modern browser on my modern machine. Thanks, Sun, great work.
- PatrickFisher, on 10/12/2007, -1/+12@zeptobyte
It doesn't work fine for everyone. Some people turn off the referring function because of privacy concerns. - ph3rny, on 10/12/2007, -0/+10they aren;t messing up their posts...
ever since someone pointed out that "digg me down" usually makes users think counter intuitively, they have been littering digg with "digg me down" posts - cyroxos, on 10/12/2007, -1/+9Why are so many people messing up their posts?
- hackwrench, on 10/12/2007, -0/+7Now where does one find an illustration of worst case scenarios and other explanation.
- inactive, on 10/12/2007, -1/+8Very true, but is this amateur hour or something? People screwing up duggmirror.com urls... People obnoxiously posting "Bury me..." People not using the reply button...
- macaddct1984, on 10/12/2007, -0/+6Good ol' BubbleSort, brings me back to my C++ high school days
- felchdonkey, on 10/12/2007, -2/+7Looks an awful lot like the "Amazing Sorting Algorithm Comparison (With Code!)" from the front page 13 days ago...
http://digg.com/programming/Amazing_Sorting_Algorithm_Comparison_With_Code - OrangeTide, on 10/12/2007, -3/+9I invented an O(1) sort, but I deleted it.
- klezmer41, on 10/12/2007, -0/+5Scratch that, make it 15 minutes.
- msgyrd, on 10/12/2007, -0/+4Some of these seem bogus. I didn't bother to analyze the code, but this site's PermSort and BozoSort seem like O(n^10). Both take infinately longer than BubbleSort, which is one of the worst sorts to implement. I'm curious if these slower ones have any purpose other than "don't ever write code like this" examples.
- u8myfoood, on 10/12/2007, -0/+4Oh the memories of my AP Java Class...
- msgyrd, on 10/12/2007, -1/+5Did you solve a few NP-complete problems with your spare time also?
- flashcat7777, on 10/12/2007, -0/+4Remind me to never use QMSort in any program I ever write.
- iAlan, on 10/12/2007, -0/+4Sorted data is much easier to search.
- klezmer41, on 10/12/2007, -0/+4OMG I'm such a dork. To think I spent 5 minutes watching different sorts "race."
- TannerLD, on 10/12/2007, -1/+5That one is a whole lot better.
- feralkid, on 10/12/2007, -0/+4Too late :)
- Scarblac, on 10/12/2007, -0/+3BozoSort is _fun_. It's a joke sort algorithm, trying to find the slowest possible. Just randomly permutate until you accidentally stumble upon a sorted list.
My best ever was "cosmic sort" - basically make a number of copies of the list, say ten, and one equally long list that you initialize to all zeroes.
Use the ten copies for error correction - constantly check them, and if one out of ten is different, re-set it so it equals the others again. Otherwise, don't use the values.
Use the list of zeroes as a list of indices into the error corrected lists. Constantly check whether this list a) contains a valid list of unique indices, and b) whether the list would be sorted if you used these indices. If so, return the list as sorted using these indices.
Now, wait for cosmic rays to flip enough bits randomly for the algorithm to finish.
Efficiency analysis is hampered by the fact that the universe will have ended way before the algorithm, affecting the frequency of cosmic rays... - bearda, on 10/12/2007, -2/+5If you're going to post a diggmirror link, make it an actual link. Two tries and you can't get it right.
- JPW420, on 10/12/2007, -0/+3@rockinthesix
Sorting is one of those things you have to do in Computer Science classes. The visualization gives you a chance to see what is going on. My computer science class in High School was Basic on an Apple IIe. We had to do a whole bunch of sorting. - rickcarson, on 10/12/2007, -0/+3I think traditionally Mergesort wasn't so popular because it involves memory allocation. It is interesting to see it beating the Quicksort, I guess Sun really has improved the speed of memory allocation a lot, and not just said they did.
Quicksort has some bad worst cases, but they are kind of pathological and unlikely to occur. But that was why I preferred Mergesort over Quicksort, plus Mergesort is a lot easier to understand. - fgsfds, on 10/12/2007, -0/+3I think BozoSort is actually an award-winning algorithm.
That is to say that some kid actually won an award for writing the slowest sorting algorithm:
DO{data.randomize();}
WHILE(!data.sorted();)
He won because it would eventually sort any dataset, but the expected time to complete the task for any meaningful set would be absurdly long.
Granted, I haven't looked at the code to see if that's the case or not, but it wouldn't surprise me. - msgyrd, on 10/12/2007, -0/+3 private int Randomize( int range ) {
double rawResult;
rawResult = Math.random();
return (int) (rawResult * range);
}
That is what Bozo's code calls on the array it sorts. It's less of an algorithm and more of a "shakespeare written by a room full of monkeys with typewriters" approach. - Brahma, on 10/12/2007, -0/+3Beware..The speed that you see here are misleading for some algorithms like merge sort. These algorithm don't do an in-place sorting meaning there is a copy of the original collection. So it is not really possible to show them in one box (cuz' you would have to modify the original set of data). Shell sort appears faster than merge sort for a medium size data whereas the reverse is usually true.
- Scarblac, on 10/12/2007, -0/+2Some are fast on average (but not on every specific possible input list), some are fast on datasets with specific properties, some are not as fast but use less memory, some are not as fast but their worst case is still fast, some are not as fast but are stable (that is, items with equal value will retain their original order), et cetera.
- ReaperUnreal, on 10/12/2007, -0/+2Heh, this is awesome, I've been looking at these since we first covered sorting in high school. Also, I go to this university, and I've gone to classes taught by this buy. But there's a better and more complete list on Jason Morisson's page.
- djdole, on 10/12/2007, -0/+2Their display code is flawed.
When it finishes, it doesn't always refresh the last frame, so the sort will appear to be incomplete. Run selection sort to the end and don't switch windows.
It'll do it with other algorithms too. - icepack12, on 10/12/2007, -0/+2Most of this source code comes from 1995. Something in Java 5.0 would be much nicer to digg.
- mlw4428, on 10/12/2007, -0/+2Merge sort seemed the quickest for me.
- Gemini25RB, on 10/12/2007, -0/+2The StoogeSort feels the need to resort things it just did. I guess it doesn't trust itself much. It's a case of excessive recursion.
The BozoSort seems to rely on semi-random numbers (the indices) for sorting. That seems like a really bad idea from all angles. - randomc0de, on 10/12/2007, -0/+2You don't need any other algorithm than Merge sort, and possibly Heap sort. As for the visualization, do them yourself with a deck of card, much, much better to learn the internals.
- enclave2, on 10/12/2007, -0/+2I'm sorry if I'm stupid, but why have all these different sorts? I know a few are just in there for fun, but why not just have the one that sorts the fastest and be done with it?
I'm not saying for this demonstration, but in real code. Is there a purpose to all the various algorithms? - jhshukla, on 10/12/2007, -0/+2http://ask.yahoo.com/20060818.html
- msgyrd, on 10/12/2007, -0/+2Ok...left Bozo and Perm running for 15 minutes in the background and neither have made any progress. I'd say they're bogus.
- yenta4shop, on 09/07/2008, -0/+1http://www.yenta4shop.co.uk/
http://astore.amazon.com/12.volt.battery.charger-2 ...
http://astore.amazon.com/5.gallon.water.bottle-20
http://astore.amazon.com/aerobed.raised-20
http://astore.amazon.com/bug.zapper-20
http://astore.amazon.com/flowtron.insect.killer-20
http://astore.amazon.com/furniture.chaise.lounge-2 ...
http://astore.amazon.com/inflatable.bed-20
http://astore.amazon.com/steam.cleaner.mop-20 - brian1001001, on 10/12/2007, -0/+1Nothing better than math/programing geek humor. HAR!
- inactive, on 10/12/2007, -3/+4LoL.... I'm in AP Computer Science right now (soph @ high school) and we just did all these algorithms.
- Curufir, on 10/12/2007, -0/+1Well, for example, the bozosort is a horrible way to sort data. HOWEVER, if you only have 3 things to sort then there's a fair chance it'll wind up faster than quicksort just because there is less overhead setting up the sort. There is no "fastest" sort, only sorts that work better with certain types of data than others. The trick is picking the right algorithm for the data.
- jalexhall1989, on 10/12/2007, -0/+1This is crazy, we JUST looked at this in my APCS class..
- oxyrubber, on 10/12/2007, -1/+2I prefer this page (not mine, but useful):
http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html - grinin, on 10/12/2007, -1/+2im drooling... not sure what time it is... or how long ive been sorting lines..... someone save us all :D
- rickcarson, on 10/12/2007, -0/+1Darn, my algorithm can only sort in O(n) time. It is called 'hashsort'.
- 022A, on 10/12/2007, -0/+1They each have different (dis)advantages. Different sorts for different circumstances.
- yogastore, on 06/27/2008, -0/+1http://astore.amazon.com/holmes.tower.fan-20
http://astore.amazon.com/honeywell.tower.fan-20
http://astore.amazon.com/10.cup.rice.cooker-20
http://astore.amazon.com/zojirushi.10.cup.rice.coo ...
http://astore.amazon.com/bug.zapper-20
http://astore.amazon.com/rat.zapper-20
http://astore.amazon.com/250gb.external.hard.drive ...
http://astore.amazon.com/500.gb.external.hard.driv ...
http://astore.amazon.com/surfboard.cable.modem-20
http://astore.amazon.com/wireless.cable.modem-20 - TiE23, on 10/12/2007, -0/+1I had a race between the sorts, Mergesort was definitely the fastest. Ones like Stoogesort were ridiculously slow.
- trolley, on 10/12/2007, -0/+1Where? I'm looking at Morrison's page but don't see them.
-
Show 51 - 65 of 65 discussions
Check out the new & improved 
© Digg Inc. 2009
— Content created and posted by Digg users is