6 ms·

Sorting Algorithm Animations

69 points by drawkbox 16y ago

vijaydev 16y ago
Excellent work!
siddhant 16y ago
Here's what different sorting algorithms sound like - http://www.youtube.com/watch?v=t8g-iYGHpEA http://www.youtube.com/watch?v=t8g-iYGHpEA Bubble sort takes the most time. :)
- InclinedPlane 16y ago
  Only because bogosort wasn't tried.
ableal 16y ago
Aldo Cortesi has some striking images going on here http://corte.si/posts/code/sortvis-fruitsalad/index.html http://corte.si/posts/code/sortvis-fruitsalad/index.html and here http://sortvis.org/ http://sortvis.org/ He explains his anti-animation rationale here: http://corte.si/posts/code/visualisingsorting/index.html http://corte.si/posts/code/visualisingsorting/index.html
bajsejohannes 16y ago
Another approach for visualizing sorting algorithms is http://sortvis.org/ http://sortvis.org/
RiderOfGiraffes 16y ago
Obviously a favorite - it turns up so often: http://news.ycombinator.com/item?id=1905940 http://news.ycombinator.com/item?id=1905940 http://news.ycombinator.com/item?id=1733814 http://news.ycombinator.com/item?id=1733814 http://news.ycombinator.com/item?id=730346 http://news.ycombinator.com/item?id=730346 http://news.ycombinator.com/item?id=555549 http://news.ycombinator.com/item?id=555549 <- This has some comments There are more: http://searchyc.com/submissions/sort+algorithm+animation?sort=by_date http://searchyc.com/submissions/sort+algorithm+animation?sor...
- drawkbox 16y ago
  Yes I saw that it was posted before and reposted based on some recent sorting articles because it is so helpful. It is like Asimov's 'The Last Question' and 'How Software Companies Die' and others because it is very interesting. An interesting static visualization from the other threads is here : http://www.hatfulofhollow.com/posts/code/visualisingsorting/index.html http://www.hatfulofhollow.com/posts/code/visualisingsorting/... I think seeing the timing and sorting in action is so helpful to understand what is going on.
- tel 16y ago
  Out of curiosity, are you keeping a log of popular HN posts or just remembering them and searching? You're always first on the scene and comprehensive, it seems.
  - RiderOfGiraffes 16y ago
    I remember and search. My memory's pretty good, and my search-fu is also usually pretty good, although not always. I'm currently looking at automating some of the process, but I do find that searching for stuff I think I remember occasionally turns up a gem I missed, and so I'm reluctant to automate it fully unless they still get found. That's why I'm starting to feed items into a Bayesian classifier to find good stuff - by my standards and according to my interests. I continue to experiment.
    - tel 16y ago
      I'd love to hear more details on your classifier. I've been interested in trying something like that for myself: a sort of automatic attention filter which brings both unmodeled outliers and probably-good articles to my attention.
jmtame 16y ago
what, no love for bogosort?
johnwatson11218 16y ago
Are there any other algorithms that can have these kinds of animations applied? Sorting works well and is easy to animate. What about graph traversal or network flow? I guess my real question is 'can all algorithms be animated in some way'? If not what decides it? If there were more than 4 dimensions I could see that being a problem right there.
- megrimlock 16y ago
  What's the best way to instrument an algorithm for visualization? Snapshot its state at periodic, well-named points, and render illustrations? I can imagine doing this with an A* search: snapshot the graph, including which nodes are open or already visited, along with the heap ranking of the next nodes to visit. You might also want to show all the newly neighboring nodes and annotate them with their updated cost estimate.
amichail 16y ago
In what sense are sorting algorithms more fundamental than say font rendering algorithms? Nowadays, they are both supplied in standard libraries and few programmers would implement either.
- olalonde 16y ago
  They are used in many more situations. A lot of problems can be reduced[1] to or contain a sorting problem. The same cannot be said about font rendering algorithms. [1] http://en.wikipedia.org/wiki/Reduction_(complexity) http://en.wikipedia.org/wiki/Reduction_(complexity)
  - amichail 16y ago
    Rendering text is even more useful than sorting.
    - olalonde 16y ago
      You are right in the sense that there is no formal definition for what makes an algorithm fundamental (AFAIK - I am no expert on the matter). However, the general consensus seems to be that since a large number of problems make use of or can be reduced to a sorting problem, it is more fundamental than font rendering which solves exactly one problem. In fact, I wouldn't be surprised if font rendering algorithms use sorting in some way.
bballbackus 16y ago
So is there an ideal case for selection sort that isn't shown or does it just suck? Edit: Never mind they explained: From the comparions presented here, one might conclude that selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic. However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

69 points by drawkbox 16y ago

Excellent work!

Here's what different sorting algorithms sound like - http://www.youtube.com/watch?v=t8g-iYGHpEA http://www.youtube.com/watch?v=t8g-iYGHpEA Bubble sort takes the most time. :)

InclinedPlane 16y ago
Only because bogosort wasn't tried.

ableal 16y ago

Aldo Cortesi has some striking images going on here http://corte.si/posts/code/sortvis-fruitsalad/index.html http://corte.si/posts/code/sortvis-fruitsalad/index.html and here http://sortvis.org/ http://sortvis.org/ He explains his anti-animation rationale here: http://corte.si/posts/code/visualisingsorting/index.html http://corte.si/posts/code/visualisingsorting/index.html

bajsejohannes 16y ago

Another approach for visualizing sorting algorithms is http://sortvis.org/ http://sortvis.org/

RiderOfGiraffes 16y ago

Obviously a favorite - it turns up so often: http://news.ycombinator.com/item?id=1905940 http://news.ycombinator.com/item?id=1905940 http://news.ycombinator.com/item?id=1733814 http://news.ycombinator.com/item?id=1733814 http://news.ycombinator.com/item?id=730346 http://news.ycombinator.com/item?id=730346 http://news.ycombinator.com/item?id=555549 http://news.ycombinator.com/item?id=555549 <- This has some comments There are more: http://searchyc.com/submissions/sort+algorithm+animation?sort=by_date http://searchyc.com/submissions/sort+algorithm+animation?sor...

drawkbox 16y ago
Yes I saw that it was posted before and reposted based on some recent sorting articles because it is so helpful. It is like Asimov's 'The Last Question' and 'How Software Companies Die' and others because it is very interesting. An interesting static visualization from the other threads is here : http://www.hatfulofhollow.com/posts/code/visualisingsorting/index.html http://www.hatfulofhollow.com/posts/code/visualisingsorting/... I think seeing the timing and sorting in action is so helpful to understand what is going on.
tel 16y ago
Out of curiosity, are you keeping a log of popular HN posts or just remembering them and searching? You're always first on the scene and comprehensive, it seems.
- RiderOfGiraffes 16y ago
  I remember and search. My memory's pretty good, and my search-fu is also usually pretty good, although not always. I'm currently looking at automating some of the process, but I do find that searching for stuff I think I remember occasionally turns up a gem I missed, and so I'm reluctant to automate it fully unless they still get found. That's why I'm starting to feed items into a Bayesian classifier to find good stuff - by my standards and according to my interests. I continue to experiment.
  - tel 16y ago
    I'd love to hear more details on your classifier. I've been interested in trying something like that for myself: a sort of automatic attention filter which brings both unmodeled outliers and probably-good articles to my attention.

jmtame 16y ago

what, no love for bogosort?

johnwatson11218 16y ago

Are there any other algorithms that can have these kinds of animations applied? Sorting works well and is easy to animate. What about graph traversal or network flow? I guess my real question is 'can all algorithms be animated in some way'? If not what decides it? If there were more than 4 dimensions I could see that being a problem right there.

megrimlock 16y ago
What's the best way to instrument an algorithm for visualization? Snapshot its state at periodic, well-named points, and render illustrations? I can imagine doing this with an A* search: snapshot the graph, including which nodes are open or already visited, along with the heap ranking of the next nodes to visit. You might also want to show all the newly neighboring nodes and annotate them with their updated cost estimate.

amichail 16y ago

In what sense are sorting algorithms more fundamental than say font rendering algorithms? Nowadays, they are both supplied in standard libraries and few programmers would implement either.

olalonde 16y ago
They are used in many more situations. A lot of problems can be reduced[1] to or contain a sorting problem. The same cannot be said about font rendering algorithms. [1] http://en.wikipedia.org/wiki/Reduction_(complexity) http://en.wikipedia.org/wiki/Reduction_(complexity)
- amichail 16y ago
  Rendering text is even more useful than sorting.
  - olalonde 16y ago
    You are right in the sense that there is no formal definition for what makes an algorithm fundamental (AFAIK - I am no expert on the matter). However, the general consensus seems to be that since a large number of problems make use of or can be reduced to a sorting problem, it is more fundamental than font rendering which solves exactly one problem. In fact, I wouldn't be surprised if font rendering algorithms use sorting in some way.

bballbackus 16y ago

So is there an ideal case for selection sort that isn't shown or does it just suck? Edit: Never mind they explained: From the comparions presented here, one might conclude that selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic. However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.