digg

Join DiggAbout

Discover the best of the web!
Learn more about Digg by taking the tour.

Visualizations of 15 Sorting Algorithms

cg.scs.carleton.ca — Compare the speeds of different sorting algorithms. Select a sorting method then click applet to watch it sort. Algorithms include: BozoSort, PermSort, StoogeSort, AMSort, BubbleSort, SelectionSort, CocktailSort, InsertionSort, ShakerSort 1 & 2, ShellSort, QSort, HeapSort, JSort, MergeSort

Bury
show profanity settings
expand all
  • rootryan, on 10/12/2007, -0/+20mergesort kicks ass. Fun page, for three minutes.
    • skotski, on 10/12/2007, -0/+33Perfect! Three minutes is just about the extent of my attention span.
    • hackwrench, on 10/12/2007, -0/+6Now where does one find an illustration of worst case scenarios and other explanation.
    • PatrickFisher, on 10/12/2007, -6/+21Hey, if anyone wants, I can make an animation that demonstrates paint drying.
    • macaddct1984, on 10/12/2007, -0/+5Good ol' BubbleSort, brings me back to my C++ high school days
    • UCFMark, on 10/12/2007, -2/+1Screw mergesort- randomsort ftw. (I think this is what they called "bozosort")
      In case you don't know what randomsort is, you basically randomly re-arrange the positions of elements, check if the data is sorted, and if it's not, do it all over again.
      Ha- probably the least efficient sort on the average, but it's simple and amusing.
    • amikael9999, on 10/12/2007, -1/+046 Free Algorithm Books:
      http://freecomputerbooks.com/compscAlgorithmBooksIndex.html
  • banter, on 10/12/2007, -27/+2digg me down
  • banter, on 10/12/2007, -23/+1digg me down again
    • 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.
  • DECwakeboarder, on 10/12/2007, -22/+1Bury me.
  • manchld, on 10/12/2007, -22/+4oh! oh! Bury me too!
  • cyroxos, on 10/12/2007, -1/+8Why are so many people messing up their posts?
  • ph3rny, on 10/12/2007, -0/+9they 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
    • exabytes18, on 10/12/2007, -1/+7Very 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...
  • felchdonkey, on 10/12/2007, -2/+6Looks 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
  • u8myfoood, on 10/12/2007, -0/+3Oh the memories of my AP Java Class...
    • Orien, on 10/12/2007, -3/+3LoL.... I'm in AP Computer Science right now (soph @ high school) and we just did all these algorithms.
  • allboox, on 10/12/2007, -6/+0May I just say that the domain hack 'algorith.ms' is up for sale at sedo :)
  • idonthack, on 10/12/2007, -9/+2@cyroxos

    It's the new fad! Everybody's doing it.
    bury me.

    edit: oh the irony
  • trolley, on 10/12/2007, -6/+0I took an algorithms class taught by Pat Morin and he's an amazing professor.
  • oxyrubber, on 10/12/2007, -1/+1I prefer this page (not mine, but useful):
    http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
  • ReaperUnreal, on 10/12/2007, -0/+1Heh, 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.
    • trolley, on 10/12/2007, -0/+0Where? I'm looking at Morrison's page but don't see them.
  • djdole, on 10/12/2007, -0/+1Their 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.
  • mlw4428, on 10/12/2007, -0/+1Merge sort seemed the quickest for me.
    • rickcarson, on 10/12/2007, -0/+2I 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.
  • rockinthesix, on 10/12/2007, -2/+0I dont want to sound stupid.. but what would be the practical application of this?
  • JPW420, on 10/12/2007, -0/+2@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.
  • randomc0de, on 10/12/2007, -0/+1You 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.
  • jalexhall1989, on 10/12/2007, -0/+0This is crazy, we JUST looked at this in my APCS class..
  • flashcat7777, on 10/12/2007, -0/+3Remind me to never use QMSort in any program I ever write.
  • Brahma, on 10/12/2007, -0/+2Beware..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.
  • klezmer41, on 10/12/2007, -0/+3OMG I'm such a dork. To think I spent 5 minutes watching different sorts "race."
  • klezmer41, on 10/12/2007, -0/+4Scratch that, make it 15 minutes.
  • msgyrd, on 10/12/2007, -0/+3Some 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.
    • fgsfds, on 10/12/2007, -0/+2I 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/+1Ok...left Bozo and Perm running for 15 minutes in the background and neither have made any progress. I'd say they're bogus.
    • Gemini25RB, on 10/12/2007, -0/+1The 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.
    • Scarblac, on 10/12/2007, -0/+2BozoSort 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...
  • msgyrd, on 10/12/2007, -0/+2 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.
  • TiE23, on 10/12/2007, -0/+0I had a race between the sorts, Mergesort was definitely the fastest. Ones like Stoogesort were ridiculously slow.
  • grinin, on 10/12/2007, -1/+1im drooling... not sure what time it is... or how long ive been sorting lines..... someone save us all :D
  • enclave2, on 10/12/2007, -0/+1I'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?
    • 022A, on 10/12/2007, -0/+0They each have different (dis)advantages. Different sorts for different circumstances.
    • Curufir, on 10/12/2007, -0/+0Well, 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.
    • Scarblac, on 10/12/2007, -0/+1Some 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.
  • icepack12, on 10/12/2007, -0/+1Most of this source code comes from 1995. Something in Java 5.0 would be much nicer to digg.
  • yogastore, on 06/27/2008, -0/+0http://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
  •  

    Login or register to add a comment

    Create a new account or login to join in the conversation on Digg. You'll also be able to Digg stories to help promote things you like.


© Digg Inc. 2008 — Content posted by Digg users is dedicated to the public domain.
DIGG, DIGG IT, DUGG, DIGG THIS, Digg graphics, logos, designs, page headers, button icons, scripts, and other service names are the trademarks of Digg Inc.