All examples By author By category About

rfrankel

Visualization of Quicksort (sequential)

What This Shows

The tree shown is a visualization of the evaluation tree of Quick Sort applied to the list (3,9,2,5,1,4,8,0,6,7). The tree has three branches at each clock tick: the left list, the right list, and the pivot. The progress in the tree aligned horizontally with the progress of the same sort shown as a weave visualization in the style of Aldo Cortesis' Sortvis. Among other things, this visualization shows why Quick Sort is a terrible algorithm: it can take a long time for the algorithm to "realize" that the sublist it is working on is already sorted.

How To Use

Drag the blue handle! A blue path will light up showing how the list is generated from the tree of evaluation states at each clock tick. It meanders around because it has to pick up pivots from earlier stages and connect them will still unsorted sublists which will be worked on at later stages. You can also click on any node and the extent of the sorting work that is accomplished by the subtree under that node will be highlighted on the right.