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

QuickSand

Reorder and filter items with a nice shuffling animation. Just specify source container and destination collection which will replace the source collection. New elements will appear with fancy scaling+alpha effect, deleted elements (non-existant in destination collection) will scale out and rearranged items will move to their destination positions.

http://razorjack.net/quicksand/

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

TinyTable JavaScript Table Sorter - 2.5KB

This updated table sorter script is easy to use and feature packed at only 2.5KB. New features include column highlighting, optional pagination, support for links, and date/link parsing. A few other features are alternate row highlighting, header class toggling, auto data type recognition and selective column sorting. More updates will follow soon.

To initialize a table sorter follow the pattern below:

var sorter = new TINY.table.sorter("sorter");
sorter.head = "head"; //header class name
sorter.asc = "asc"; //ascending header class name
sorter.desc = "desc"; //descending header class name
sorter.even = "evenrow"; //even row class name
sorter.odd = "oddrow"; //odd row class name
sorter.evensel = "evenselected"; //selected column even class
sorter.oddsel = "oddselected"; //selected column odd class
sorter.paginate = true (false); //toggle for pagination logic
sorter.pagsize = 15 (20); //toggle for pagination logic
sorter.currentid = "currentpage"; //current page id
sorter.limitid = "pagelimit"; //page limit id
sorter.init("table",1);

Before initialization, a new table sorter object must be created. The parameter taken by TINY.table.sorter is the variable name used for the object. The object.init function takes 2 parameters: the id of the table and the initially sorted column index (optional). If you want to exclude a column from sorting add class=”nosort” to the appropriate table header. Table styling is completely customizable via the CSS.

TinyTable has been tested in Firefox 2/3, IE 6/7/8, Opera, Safari and Chrome. Please send bug reports to michael@leigeber.com with the subject “BUG REPORT”. This script is available free of charge any project, personal or commercial, under the creative commons license and is offered AS-IS, no free support provided. Click here to inquire about paid support.

Click here for the demo.

Click here to download the source code.

http://www.leigeber.com/2009/03/table-sorter/