Sunday, March 20, 2011

Sunday Numbers 2.0, Vol. 5:
Sorting animations.

As Donald Knuth said, "An algorithm must be seen to be believed." In some browsers, you can click on the pictures to watch an animation of some famous sorting algorithms.

Here is a video from The You Tubes of heapsort. This is a link to another animation of Heapsort, which puts in a heap sorted backwards, then takes the big values at the front of the line and moves in in exact order into the back of the line.

Here is a YouTube selection for Quicksort. Note that some of the lines are green, which means in the proper position, and some are in blue, which means not yet perfectly sorted. While the project appears to be try to set things up from left to right, you'll notice very early on a green line This is a link to another animation of Quicksort, which picks a single value, puts it in the proper position, with everything smaller than the value in front of it and everything bigger after it. This effectively splits the data set into two parts to be sorted yet again. This is called a divide and conquer algorithm.

My friend Ken sent me a link to a bunch of animating in place sort algorithms. These include Heapsort and Quicksort, as well as merge, bubble, shell and others.

Thanks to Ken. Fun stuff, if you like that sort of thing.

(Nerd puns. Tee hee!)


Anonymous said...

In my browser at 7:04pm Pacific time, the animated GIFs have a file type of PNG. Normally my browser has no trouble playing animated gifs.

Matty Boy said...

Thanks for reporting in, anonymous. I tried to fix the .gif problem, but the easier solution was to nick a couple of videos from the You Tubes.