Mike Bostock, the author of d3.js, has a similar post in which he uses angled sticks to indicate sorting order, and also touches on some other algorithmic visualizations.
The use of the vertical axis here is brilliant! I've seen visualizations where time is one of the axes, but showing a random sampling of arrays really lets you see the "ensemble behavior" of the algorithms.
I really wish the frame rate was every n comparisons or seconds instead of the rate of the outer loop. In the first four, the boundary between sorted and unsorted should accelerate and the progression of merge sort should be constant. Heapsort should also accelerate, but at a different rate from the n^2 sorts. It would be so much more satisfying.
Good stuff, except for the rainbow color scales [1]. I'd much prefer to see the same in viridis [2] or something similar. The color boundaries on the rainbow scale are not perceived uniformly by human eyes (there might even be a cultural bias at play, i.e. we may distinguish blue from green more readily than different shades of blue, even if they may be objectively at the same distance)
Nope, thankfully no cultural bias in the distinction of hues and shades (and especially gradients), only in the number of standard words to describe them. This makes it easier to be sure of how swell viridis/inferno are.
Sorting is about relative distance anyway. “Am I closer than you to negative infinity?” Why does having absolute perception matter? (Indeed, all but radix sort use comparison-based strategies. There’s some notion of a “less than” operation being used to make decisions.)
Viridis is useful for scientific plots where scale perception is important in making a good conclusion. I don’t think demonstrating sorting requires the same perception.
One real problem in using the hue component of HSL is that it wraps around perceptually by design. There's no "greatest" or "least" hue. And the ordering isn't exactly intuitive because we don't perceive colors based on the order of their respective wavelengths on the EM spectrum. Varying the saturation or luminance component while keeping the other two constant makes it much easier to perceive the relationship of two colors at a glance. Or just take a gradient between two appropriately contrasting colors which is exactly what viridis is about.
Nit: "distance" in color space is fiendishly difficult to define. It's not as simple as treating RGB as cartesian coordinates and computing the distance algorithm.
Compared to other visualization, having the extra axis dimension just means what, that the sorting is being done as if each row was an independent sort, and all rows are being sorted simultaneously?
Yeah it's one sort per line all running in parallel. The lines start off shuffled independently and have the same algorithm run on each line.
A nice side effect of this is that some lines of quicksort finish much more quickly than other lines. That is the major downside to quicksort (other than being non-stable in its fastest versions).
That was a lot of fun. I remember seeing the visualisations from lowest to highest on a bar chart but this gives a different perspective on how the algorithms work.
These are neat but it's a bit odd to call heapsort and mergesort bizarre. Sure if you just think about them as operating on arrays they would seem strange, but if you think about them more abstractly they make complete sense.
Create a two-dimensional array of width w and height h. Fill each row of the array with the numbers 1..w randomly shuffled. Pick a sorting algorithm, implement it so that you can run it one elementary sorting step at a time and observe the partial result. For each row in your array, execute a single step of your algorithm. Store the partial result as an image, with the elements of the array interpreted as the hue component of a HSL color coordinate. Repeat until the algorithm has halted for every row in the array. Make an animation out of the resulting frames.
https://bost.ocks.org/mike/algorithms/