Sorting Algorithm Animations | Hacker News Reader

Sorting Algorithm Animations

sorting-algorithms.com

69 pointsdrawkbox18 comments

Open articleView on HN

Obviously a favorite - it turns up so often:

http://news.ycombinator.com/item?id=1905940

http://news.ycombinator.com/item?id=1733814

http://news.ycombinator.com/item?id=730346

http://news.ycombinator.com/item?id=555549 <- This has some comments

There are more:

http://searchyc.com/submissions/sort+algorithm+animation?sor...

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/...

I think seeing the timing and sorting in action is so helpful to understand what is going on.

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.

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.

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.

Here's what different sorting algorithms sound like - http://www.youtube.com/watch?v=t8g-iYGHpEA

Bubble sort takes the most time. :)

Only because bogosort wasn't tried.

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

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.

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.

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)

Rendering text is even more useful than sorting.

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.

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.

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.

what, no love for bogosort?

Aldo Cortesi has some striking images going on here http://corte.si/posts/code/sortvis-fruitsalad/index.html and here http://sortvis.org/

He explains his anti-animation rationale here: http://corte.si/posts/code/visualisingsorting/index.html

Excellent work!

Reply on news.ycombinator.com