Sorting Algorithm Animations

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.

tel2• 16 years 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.

RiderOfGiraffes2• 16 years 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.

jmtame• 16 years ago

what, no love for bogosort?

johnwatson11218• 16 years 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• 16 years 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.

amichail2• 16 years 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.

olalonde2• 16 years 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)

amichail2• 16 years ago

Rendering text is even more useful than sorting.

bballbackus• 16 years 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.

Sorting Algorithm Animations

Related Stories