Sunday, September 05, 2010

Visualising sorting algorithms

This is another one of my rare technical posts, as opposed to news of which countries I've been visiting.

If you're in computer science, you've probably seen an animation of sorting algorithms, maybe heard a rendition, or seen a visual representation. I have, somewhat by accident, discovered a different way to visualise a sorting algorithm: plot points for memory accesses, with address on the X axis and time (counted by accesses) on the Y axis, and different colours for reads and writes. It produces some rather pretty pictures. Note that these are not to scale relative to each other - the Y axis has been compressed to fit the entire sort into a fixed height.

Ye olde bubblesort. Some of the patterns are an optical illusion due to aliasing, but the green spikes are a feature of the algorithm.

Insertion sort - the version optimized for mostly sorted content. Although the data is random, you can see that in many cases it reduces the search distance.Shellsort, clearly showing the phases.

Selection sort:Heapsort: the solid lines at the top are the heap-building phase, while the rest shows the extraction. Note the very slight slope to the bottom-right line: as the heap gets smaller, the heap extraction gets faster, but only as O(log N).
Divide-and-conquer algorithms have a pretty fractal nature. This is quicksort - the perturbations in the fractal indicate the random selection of pivots (it just picks the middle, rather than median-of-3). Mergesort: this diagram is twice as wide as the others because it uses temporary storage on the right.



18 comments:

Tim said...

Beautiful. I want these as art prints.

Unknown said...

Nice. Care to share source?

Bruce Merry said...

Yeah I hope to have source on my website at some point - still want to polish it and document it a little better.

. said...
This comment has been removed by the author.
Unknown said...

Awesome visualization. Most intriguingly (to me) is that the quadratic algorithms have an obvious parabolic shape/area.

Expert Snowboarder said...

awesome

Ilmari Heikkinen said...

Ooh, pretty! Love the bubblesort one.

I once used a similar visualization idea for seeing how glibc qsort compares to the qsort described in K&R. ( Here's the writeup if you're interested.)

Anonymous said...

Very nice! One question: Would the outcome of this be affected by the underlaying OS and it's memoryhandling (paging etc)?

Bruce Merry said...

ekas: it's showing virtual addresses and the "time" axis is simply the count of accesses rather than real time, so it's not affected by anything the OS does.

Parijata D. Mackey said...

Very interesting... I approve of your thought processes.

Steve Hanov said...

This is great because you can see which ones optimize for locality. If you highlight CPU cache misses in there, this would be revelutionary.Then we could see which one is best on real hardware.

Anonymous said...

Thanks Bruce. Spotted your post on Hacker News. I was in Smuts 2004-2005 but I remember Jared Licina once going on about your brilliance! Joran Greef.

Unknown said...

Sweet, Bruce :) I'm glad you did the other sorting algorithms. Some of them are really intriguing to look at: bubble sort, heap sort and quick sort in particular.

desert1940fox said...

pretty cool, those visualizations are awesome

Jorge Sánchez said...

t-shirts....I wanna one !

Unknown said...

That is really beautiful. Great!

Prashant said...

Beautiful way of visualizing algorithms .

If you want to visualize sorting algorithms in Java Applet form ( animated ) , also take a look at :
http://http://www.thelearningpoint.net/computer-science
( Java applet visualization for popular sorting algorithms - Bubble sort , merge , quick , insertion , shell sort )

jason said...

good post