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

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.

## 17 Comments:

Beautiful. I want these as art prints.

Nice. Care to share source?

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

This comment has been removed by the author.

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

awesome

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

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

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.

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

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.

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.

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.

pretty cool, those visualizations are awesome

t-shirts....I wanna one !

That is really beautiful. Great!

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 )

Post a Comment

<< Home