Digg

Donkeys and Elephants and Delegates,oh my!
Check out the most popular Elections 2008 content on Digg.

Amazing Sorting Algorithm Comparison (With Code!)

cs.rit.edu — The animations on this website demonstrate how effective a good sorting algorithm can be. Source code in java is provided! Some more sorts to check out: http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html .

Bury

knyghtfyre 1 year 295 days ago, made popular 1 year 295 days ago

1772 diggs
digg it

aplusbi, on 10/12/2007, -4/+21I would have liked to see some other sorting methods, especially non-comparison based sorting (bucket sort, radix sort, etc). Still it is a good demo!
- VolsFan, on 10/12/2007, -1/+60Ask, and you shall receive! Here's a list of a lot more sorts that we used way back when I was taking freshman CS classes. Same applet, just a wider selection of algorithms.
  http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
- greyghost487, on 10/12/2007, -13/+8I wouldnt call this AMAZING, but a good visual demo none the less.
  
  Where is the Radix?
  
  in a Sorting algorithm throw down, radix makes bubble sort his bitch every time.
- negativefx, on 10/12/2007, -13/+12would have dugg this article if the ***** idiot didn't use the word amazing.
  
  @greyghost: lol...love the radix comment.
- MattL920, on 10/12/2007, -7/+8It's amazing how many articles do that
- MattL920, on 10/12/2007, -1/+20"in a Sorting algorithm throw down, radix makes bubble sort his bitch every time."
  
  Isn't that like saying Lance Armstrong would make a one-legged cripple his bitch every time in a race?
- asteron, on 10/12/2007, -12/+6DUGG DOWN for the superfluous "AMAZING". This scourge must be stopped! It's getting ridiculous to think everything on the internet is "amazing". That is such an annoying digg tactic.
- Caerbannog, on 10/12/2007, -1/+5@aplusbi: Bucket sort, radix sort, and other non-comparison-based sorts aren't as easy to visualize because they don't happen in place, and would really require a visualization of the intermediate memory buffers as well to get a good impression of what is happening (which is complicated, because the size of the auxiliary buffer in those algorithms is arbitrary).
  
  (this is obvious from the radix sort linked above, the intermediate steps are happening off-screen)
- ByteGuerilla, on 10/12/2007, -2/+1Bubble sort animation didn't seem right to me. Bubble sort compares adjacent items and switches them round if they're not in the right order. The animation wasn't doing that. Haven't looked at the code yet, but the animation wasn't right.
- fluxion, on 10/12/2007, -0/+5@ByteGuerilla
  
  the bubblesort looked right. watch it closely, it selects the largest of the first pair, then moves down the list looking at each pair and keeps picking up the larger item before eventually depositing the largest at the bottom. then it starts over.
- ByteGuerilla, on 10/12/2007, -1/+2Yeah you're right. I just did a bubblesort IRL with a deck of cards and it was doing exactly that. My bad.
roominator, on 10/12/2007, -1/+14We've been going over some of these algorithms in my AP Comp Sci course. It's interesting to see them visually running.
- sirsteveh, on 10/12/2007, -3/+5For AP Comsci (got a 5 last year, AB), you just need to know quick, merge, bubble, selection, and insert. They've got some more interesting ones here. Take a look at radix, it's pretty nifty. Looks like "shear sort" warrants some investigation as well.
xtmno3, on 10/12/2007, -0/+5I wish we would have this sort of demo in my Algo. Analysis class. Comparing runtimes of algo's just doesn't seem to mean as much if you can't visualize it.
- iamcanman, on 10/12/2007, -8/+3Your unintentional pun just made me snort coffee. Ouch!
strictnein, on 10/12/2007, -3/+4Actually a little more interesting than I thought it would be. My first thought was "Yay for Freshman Comp Sci" but the animations are decent.
SteelChicken, on 10/12/2007, -3/+1yeah that was nice to see the visual effects.
ive forgotten alot of the math involved. of those sorts, which one is on average the fastest?
- ABadInAlbany, on 10/12/2007, -0/+2uhhh isn't it obvious by RUNNING them? the transpose and the shear are vastly faster than bubble or quick, and given the population of data provided, the shear by a nose.
- Heretushi, on 10/12/2007, -1/+2In a LOT of real world situation, a combination of method is usually the fastest. Each algorithm might be good in a situation but they rarely are good every time.
- mipadi, on 10/12/2007, -1/+18You don't even have to run them—that's what Big O notation is for!
- bearda, on 10/12/2007, -1/+14@abadincrotch
  
  Keep in mind the last two algorithms are based on parallel execution, while the first two were single threaded. I would have liked to see a way to adjust the number of parallel processes to make a more general comparison. Parallel sorting is great if you have the capability, but quicksort gets the job done more often than not.
  
  Andrew Beard
- msgyrd, on 10/12/2007, -1/+29Bubble sort is fastest.
  
  Assuming the data is already sorted. :)
- Corneliusm, on 10/12/2007, -1/+1This applet reminds me of some fun times I had in the algorithms class I took in college.
  
  The easy sort algorithms many comp sci students learn their first semester are often the slowest (like bubblesort, insertion, and selection sort), which all have upper bounds of O(n^2).
  
  Oddly enough, more complicated sorting algorithms can easily top the methods mentioned above. Quicksort, mergesort, heapsort (and some others I forgot) have upper bounds of O(n*log(n)). With some of these, you can use recursion to implement the algorithm easier (or with less space complexity).
  
  The fastest sorting algorithms (counting, pigeonhole, radix, bucketsort) are linear (O(n)) in complexity because they don't rely on comparison. However, they each have their caveats (like relying on extra storage, discrete elements, etc).
  
  There are other important advantages besides speed. Stability for one (whether elements with equal keys are in their original order after sorting). Whether the algorithm does the sorting in-place (rather than copy to somewhere else) is another important feature to have (what good is a fast algorithm if you keep running out of memory?).
  
  Any decent CS program should cover the complexities of sorting. It might not be used later in your career, but does help you understand computational complexity and why algorithms are so important.
inkyblue2, on 10/12/2007, -7/+32"Amazing"

you keep using that word. i do not think it means what you think it means.
- bentheo, on 10/12/2007, -3/+1agreed
- Phocion55, on 10/12/2007, -5/+4"Amazing" in title = better front page chances
- haydentech, on 10/12/2007, -5/+3Not if I'm voting -- it gets an insta-bury for "amazing" or exclamation points in the title. However, I will say that this article is notably more interesting than the typical amazing/exclamation faire.
- UglyBunny, on 10/12/2007, -0/+1@ haydentech
  
  Yet you still click links which you've insta-buried...
emlyn, on 10/12/2007, -0/+2I agree about the comparison based sorts. The lower bound time complexity of comparison based sorts is O(n log(n)). Bucket sort, radix sort, etc can be linear time complexity.
acomj, on 10/12/2007, -7/+2Bahh-
Back in my day we did sort comparisons in C with none of these fancy graphics. Actually we had to code many algorithms and analysize them with different data sets (random, almost sorted, sorted backwards). The sort you use depends on a number of factors.

One of my favorite ways to sort in java when I get one element at a time is to use the collections, tree function. Just add to tree and it inserts in order.

We had quick sort, heap sort, bubble sort, select sort.
These sorts are new to me, although they seem for multi processor machines which are more prevelent today.
# Odd-Even Transposition Sort
# Shear Sort i
- transeunte, on 10/12/2007, -1/+18"Bahh-
  Back in my day we did sort comparisons in C with none of these fancy graphics."
  
  That's nothing! Back in my day we were too busy fighting dinosaurs to bother with sort algorithms!
- Canthros, on 10/12/2007, -1/+16Dinosaurs? Ha! Luxury!
- msgyrd, on 10/12/2007, -0/+2Your day must not have been too long ago. I was in Algorithms 2 years ago and we still did it in C.
- Sparticuz, on 10/12/2007, -0/+1I'm in computer science one and I'm learning C right now!
- Gemini25RB, on 10/12/2007, -0/+1"One of my favorite ways to sort in java when I get one element at a time is to use the collections, tree function. Just add to tree and it inserts in order."
  
  It's really easy to write code that inserts random values into the correct place. I bet Java just uses a Heap based on the standard compareTo(Object o) method.
thydzik, on 10/12/2007, -11/+3cool
- repruhsent, on 10/12/2007, -11/+5Don't put so much text in your comment next time; when your comments are THIS long, people tend not to read them.
- Sparticuz, on 10/12/2007, -0/+1When you write that about someone's comment, people tend to read it anyways.
celestial, on 10/12/2007, -8/+1why am i not surprised this came from my school?
- yomommanow, on 10/12/2007, -5/+1some great stuff... nice to see the animated comparisons.
  one thing though... seems they need to teach a little something about meaningful variable names and comments... makes code a lot more maintainable/reusable when u come back to it in the future or when someone else tries to decipher it. single letter names in loops are a nightmare 6 months later when u have to work through everything again just to figure out how the code does it.
- Chandon, on 10/12/2007, -0/+4Single letter variable names are frequently more readable.
  
  Consider the following C code:
  
  for(int i = 0; i < length; ++i) { ... }
  
  versus this:
  
  for(int iLoopCounter = 0; iLoopCounter < iTotalLength; iLoopCounter = iLoopCounter + AMOUNT_TO_INCREMENT_LOOP_COUNTER) { ... }
- Gemini25RB, on 10/12/2007, -0/+3@yomommanow
  
  I do agree that meaningful variable names are nice (as is commented code), but I think it has almost become standard that for-loop counters be named "i". It doesn't say much, but if it is a counter, it shouldn't take much to figure out.
SteelChicken, on 10/12/2007, -7/+2God you guys sure like to take jabs at people, dont ya? I said I didn't remember the math, and yes it was obvious that bubble was uber slow, but the other 3 ran about the same speed, and thats just ONE case. I can't read the math, so can someone please say which one was the fastest ON AVERAGE from the math provided?

You guys are so quick to insult someone...just because they dont remember their Log notations and crap. Internet nerd tough guys.
- xtmno3, on 10/12/2007, -2/+1Fastest on average is given by the n^2 or nlogn indications. If you compare graphs of these functions you will find out which is fastest on average. Of course, there can be worst-case scenarios for each where the data could already be sorted (or other things based on the algo) which cause on to perform terribly compared to average.
- covidiu, on 10/12/2007, -0/+5n is the size of the data. O(n^2) or O(n log n) is the complexity of the algorithm (the number of elemental operations) relative to the size of the data.
  
  Go to http://www.sunsite.ubc.ca/LivingMathematics/V001N01/UBCExamples/Plot/calc.html, wait for the Java applet to load and hit the "Clear" button. Then, in the "y =" textbox enter "x^2" and press "Plot", then enter "x * ln x" and press "Plot" again. You will notice that the first function is steeper (it raises quicker when x raises). So basically, O(n^2) - bad, O(n log n) - good.
  
  Don't know why, but quicksort always seemed counter-intuitive to me. I always preferred to write the heapsort algorithm instead. My new favorite is combsort which is basically bubblesort with a twist (see the Wikipedia entry).
- metalstorm, on 10/12/2007, -0/+1@steelchicken
  
  In analysis the average case doesn't matter as much as worst case, or expected worst case. The quicksort they give should really be randomized quicksort if it isn't already. Then you get an expected worst case of O(nlogn). This is the fastest that can be done in comparison based sorting (without parallel processing) as shown by lower bound analysis.
  
  However, non-comparison algorithms such as radix sort aren't limited by this lower bound.
- Gemini25RB, on 10/12/2007, -0/+1The thing with Big O notation is that it neglects everything except the highest order value. An algorithm that is 0(n^2) may seem like a terrible idea. But if you know that the real runtime is t = (0.15)n^2 + 5, then it will outperform many other algorithms (of all Big O classifications) for smaller values of n.
  
  Big O notation is good for generalizing the HUGE cases, but if you are working with a capped size, it is often worth more efficiency to analyze your algorithm for efficiency based on the max and average sizes and go from there.
banderbe, on 10/12/2007, -7/+2Clicking on that link made Firefox 2.0 crash.
- ez4me2c3d, on 10/12/2007, -2/+8FF 2.0 does not crash for me.
Brahma, on 10/12/2007, -0/+1Might not be rocket science but the thought process that went to this is good. I definitely loved the concept.
loconet, on 10/12/2007, -3/+6Digg reminds me of one of my uncles. With excitement, always telling me about stuff most informed people have known about for years.
obrie, on 10/12/2007, -1/+7Wel, I didn't think a page for a course I took 4 years ago at RIT would ever appear on Digg. If you want to see the real sorting page for our CS Labs check out

http://www.cs.rit.edu/~vcss233/pub/lab05/sorts.html

That page contains comparisons for insertion, shell, quick sort, bubble, selection, heap, and merge.
over9000, on 10/12/2007, -1/+1There are some more here
http://cg.scs.carleton.ca/~morin/misc/sortalg/
tablatronix, on 10/12/2007, -0/+1I found these a few years ago when learning about sort alogorithms, they were very helpful in visualizing the differences between them. They are fun to watch as well.
lostlogic, on 10/12/2007, -1/+5Just some information here -- the applet really is running the sorts, but it's artificially simulating the differences between the parallel and non-parallel algorithms. It's a pretty cool demo, but after reading the code, stripping the pauses and running it locally in a sort testing container, here is how the sorting algorithms _as coded_ actually perform without pauses (times are for sorting 10000 elements, in milliseconds):
Quick Sort: 5, 5, 5
Odd-even Transposition Sort: 446, 449, 437
Bubble Sort: 503, 498, 512
Shear Sort: 64, 65, 64
So, if you actually had n/2 processors for odd-even transposition, or sqrt(n) for shear sort, you could see performance somewhere near what the applet shows, but otherwise, no. Even with that many processors, you still have latency to deal with. Overall, I love quick sort.
mikewhalley, on 10/12/2007, -2/+2AMAAAAAAAZING story!
^^^^^^^^^^^^^^^^^^^^^^

But seriously, it's nice to see the way these sorts work visually. Makes it more interesting than seeing my computing teacher try his best to visualise it on the backboard ;-)
farr, on 10/12/2007, -5/+1There is no animation for me, just boxes full of static different length lines.

FF 2, Java 1.5, XP...
- inkubux, on 10/12/2007, -2/+1right click on the boxes ;) they will sort the static
- ccheath, on 10/12/2007, -1/+5try clicking on the boxes it will start the sorting applet
- Derrekito, on 10/12/2007, -1/+2you have to be smarter than your windows machine...
gerrylazlo, on 10/12/2007, -2/+1Here is an excellent page that allows more side by side comparisons of other algorithms.
http://cg.scs.carleton.ca/~morin/misc/sortalg/
Pyroice04, on 10/12/2007, -0/+4Here is the best that I've seen so far:
http://thomas.baudel.name/Visualisation/VisuTri/index.html

It allows you to compare up to 6 different types of the following sorting algorithms:
* Selection Sort
* Bubble Sort & Shaker Sort
* Insertion Sort, Dichotomic insertion (1 & 2)
* Heap Sort
* QuickSort & Quicker Sort
* In place stable sort
* ShellSort
* Dobosiewicz sort

Also, you can vary the data set's initial organization:
* Random
* Sorted
* Sorted Inverted
* Almost Sorted
* Almost Inverted
* Triangle
* Inverted Triangle
* Bell Shaped
* Custom
dlogic, on 10/12/2007, -3/+1this is old..seen many times
rovertly, on 10/12/2007, -3/+2sorting algorithms?
pleaseee. don't send this *****.
no one knows what this even means!
NateFishler, on 10/12/2007, -1/+2Yay! I'm so excited so see an explanation of standard sorting algorithms's and their speeds for all of those stupid-ass diggers that are either too lazy / stupid to go to college and take a course that goes over this!
intehnet, on 10/12/2007, -1/+2wow, what are the odds of this? I've got an exam on sorting algorithms in 5 days :)
Heap sort is also worth a look, and if you're into sadomasochism, check out AVL tree's and b-tree methods of keeping elements sorted as they're added to a data structure.. :)
mdmadph, on 10/12/2007, -1/+1i'm thinking this digg could have one of the highest digg-number to comment-number ratios in history.

(digg number comment-number... highest ratio... think I got that right. aw, ***** it.)
kaffiene, on 10/12/2007, -0/+0This applet has been around for years.
osbjmg, on 10/12/2007, -2/+1Very cool, although I could have used without the "amazing" grandstanding.
Derrekito, on 10/12/2007, -1/+1I remember bubble sorts... ahhh I hated them. Even in highschool I could see better ways of doing a sort... but I suppose I have to follow instructions to make the teacher happy....
AceTracer, on 10/12/2007, -1/+1Flashbacks of my 9th grade Pascal programming class.
RandomInsano, on 10/12/2007, -1/+1I've seen this page. My prof for intro computer science showed us this. Good stuff
zacmccormick, on 10/12/2007, -1/+1dugg for those animations!
webshared, on 10/12/2007, -1/+1As I think it is impossible to sport array of N items faster that O(N*ln(N)).
So quicksort is the fastest for simgle-prosess algos.
Jonty, on 10/12/2007, -0/+2Excellent! This was featured on digg AGES ago and I've been looking for it for a while, unsuccessfully. But here it is. Thanks!
allboox, on 10/12/2007, -1/+1May I just say that the domain hack 'algorith.ms' is up for sale at sedo :)
yogastore, on 06/30/2008, -1/+0http://astore.amazon.com/la.crosse.atomic.clock-20
http://astore.amazon.com/la.crosse.technology.wire ...
http://astore.amazon.com/upright.bagless.vacuum-20
http://astore.amazon.com/dyson.upright.vacuum-20
http://astore.amazon.com/hoover.bagless-20
http://astore.amazon.com/hoover.canister-20
http://astore.amazon.com/pyrex.storage-20
http://astore.amazon.com/pyrex.storage.lids-20
http://astore.amazon.com/inflatable.bed-20
http://astore.amazon.com/aerobed.inflatable.bed-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.

Amazing Sorting Algorithm Comparison (With Code!)

Login or register to add a comment