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.


http://blog.brucemerry.org.za/2010/09/visualising-sorting-algorithms.html

Sorting Algorithm Animations

These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to:

• Show how each algorithm operates.
• Show that there is no best sorting algorithm.
• Show the advantages and disadvantages of each algorithm.
• Show that worse-case asymptotic behavior is not the deciding factor in choosing an algorithm.
• Show that the initial condition (input order and key distribution) affects performance as much as the algorithm choice.

The ideal sorting algorithm would have the following properties:

• Stable: Equal keys aren't reordered.
• Operates in place, requiring O(1) extra space.
• Worst-case O(n·lg(n)) key comparisons.
• Worst-case O(n) swaps.
• Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

http://www.sorting-algorithms.com
http://www.nihilogic.dk/labs/sorting_visualization