Sorting Visualizations

https://imgur.com/gallery/RM3wl

by infodroid • 9 years ago

651 35 9 years ago

imgur.com

d_watt• 9 years ago

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

What was used to generate the gifs?

jas_far• 9 years ago

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

jwdunne• 9 years ago

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.

heydenberk• 9 years ago

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/

hunta2097• 9 years ago

Wow - those are simply amazing.

panic• 9 years ago

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.

_asummers• 9 years ago

My favorites have always been the folk dance versions!

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

BugsJustFindMe• 9 years ago

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

buster• 9 years ago

Honestly, this is soo brilliant, thanks for sharing!

afshinmeh• 9 years ago

I wonder how they created this visualization?

Sharlin2• 9 years ago

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.

sidcool• 9 years ago

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

alasano• 9 years ago

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

hellofunk• 9 years ago

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.

jaimex2• 9 years ago

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

IgorPartola• 9 years ago

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

emilioolivares• 9 years ago

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

jasonwelk• 9 years ago

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?

cup-of-tea2• 9 years ago

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

0xBABAD00C• 9 years ago

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)

sillysaurus32• 9 years ago

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.

reikonomusha• 9 years ago

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.

Sharlin2• 9 years ago

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.

XaspR8d• 9 years ago

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.

microcolonel• 9 years ago

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.

XCSme• 9 years ago

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

sillysaurus32• 9 years ago

Those are mp4's.

cup-of-tea2• 9 years ago

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.

pvillano• 9 years ago

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.

fredley• 9 years ago

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

gondo• 9 years ago

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

caspervonb• 9 years ago

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.

mgalka• 9 years ago

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

greggman• 9 years ago

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

taozhijiang• 9 years ago

really amazing job!

Sorting Visualizations

Related Stories