Sorting Visualizations | Hacker News Reader

Sorting Visualizations

imgur.com

651 pointsinfodroid35 comments

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.

https://bost.ocks.org/mike/algorithms/

Wow - those are simply amazing.

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.

My favorites have always been the folk dance versions!

https://www.youtube.com/watch?v=ROalU379l3U

My favorite, possibly by nostalgia, is the 1980 film "Sorting Out Sorting". https://www.youtube.com/watch?v=SJwEwA5gOkM

Honestly, this is soo brilliant, thanks for sharing!

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)

[1] https://visual.ly/blog/rainbow-color-scales/

[2] https://cran.r-project.org/web/packages/viridis/vignettes/in...

Edit:

Here's my demo, in Viridis: http://gph.is/2xZnKxl

(Generated in ipython + numpy + matplotlib + seaborn)

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.

So, yes, everything you said, and then some.

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.

Or if you still want a rainbow to satisfy personal design desires, cubehelix and HCL both provide great perceptively-balanced scales.

That said, I usually prefer subsets, like viridis.

> there might even be a cultural bias at play,

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.

I like this project, reminds me a lot of https://www.youtube.com/watch?v=kPRA0W1kECg

What was used to generate the gifs?

"The algorithms were written in C# using visual studio, and i used GIMP to make the actual gifs." https://imgur.com/user/FishyMcFishFace

Challenge: look at just the visualization and NAME! THAT! ALGORITHM!

Oh, this, this is a great idea. Do it!

one of my favourite https://www.youtube.com/watch?v=bcwwM6EoveA

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.

Well, these are really beautiful. I've seen a lot of sorting visualizations, but these were the first that kind of took my breath away.

just throwing this out there. found it was not clear how to count operations for more complex algos

http://greggman.github.io/doodles/sort.html

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.

What are the odds, just posted one myself with audio, and intended to have level of details but there are just balls and bars at the moment.

Think I'll adopt a color scale for the denser datasets, looks great.

Very cool, I love how new ways of visualising sorting keep appearing.

My favourite sorting algorithm is multiverse sort, which runs on O(n): First, check if the list is sorted. If not, destroy the universe.

I wonder how they created this visualization?

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.

Really cool! Is the code posted anywhere? Would like to see how some of these work.

I always have difficulty mapping the algorithm with visualization. Probably d3-dyslexic.

You should make en entry on Urban Dictionary for "dddyslexic"

really amazing job!

The GIFs take forever to load, bad format chosen for displaying the animations.

Those are mp4's.

Reply on news.ycombinator.com