What is Digg?82 Comments
- VolsFan, on 10/12/2007, -1/+61Ask, 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 - msgyrd, on 10/12/2007, -1/+29Bubble sort is fastest.
Assuming the data is already sorted. :) - inkyblue2, on 10/12/2007, -7/+32"Amazing"
you keep using that word. i do not think it means what you think it means. - 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? - mipadi, on 10/12/2007, -1/+18You don't even have to run them—that's what Big O notation is for!
- 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!
- 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!
- 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 - 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.
- 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. - ez4me2c3d, on 10/12/2007, -2/+8FF 2.0 does not crash for me.
- 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.
- 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). - 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. - 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 - 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. - ccheath, on 10/12/2007, -1/+5try clicking on the boxes it will start the sorting applet
- 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) - 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. - 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.
- 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.
- 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.
- 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.
- 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!
- 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.
- Sparticuz, on 10/12/2007, -0/+1When you write that about someone's comment, people tend to read it anyways.
- 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.
- MattL920, on 10/12/2007, -7/+8It's amazing how many articles do that
- 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. - 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. - 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.
- 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. - Derrekito, on 10/12/2007, -1/+2you have to be smarter than your windows machine...
- Sparticuz, on 10/12/2007, -0/+1I'm in computer science one and I'm learning C right now!
- 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.
- 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!
- inactive, 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.. :) - inactive, 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.
- UglyBunny, on 10/12/2007, -0/+1@ haydentech
Yet you still click links which you've insta-buried... - AceTracer, on 10/12/2007, -1/+1Flashbacks of my 9th grade Pascal programming class.
- 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....
- strictnein, on 10/12/2007, -4/+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.
- RandomInsano, on 10/12/2007, -1/+1I've seen this page. My prof for intro computer science showed us this. Good stuff
- 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. - 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/ - zacmccormick, on 10/12/2007, -1/+1dugg for those animations!
- 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. -
Show 51 - 79 of 79 discussions
The Digg Toolbar for Firefox lets you Digg, submit content, and keep track of Digg even when you're not on the Digg site. Download the official 
© Digg Inc. 2009
— Content created and posted by Digg users is