One of my projects this week has been to play with a visualization of the Quicksort algorithm. This algorithm was developed by Sir Charles Antony Richard Hoare in 1960. It is embedded below from this site on googledrive.
Available Here
In addition to playing with d3 more, I wanted to put this together so as to provide a more interactive/dynamic approach that what I have come across yet. Mainly, be able to see the little values float on either side of the pivots as they are chosen, as (for me at least) this helps to reinforce how the algorithm works. So that's what this does.
(made before I lightened the grey for sorted values)
Implementation-wise, this was a little tedious, but still enjoyable to putz with. The entire drawing area is within a single svg viewport to simplify moving things from one layer/step to another. This is also using d3 transitions on the color, which works pretty well, and the default easing in d3 results in an effective little stomach drop as the bars move down the screen.
This visualization does not include the "replace-in-place" component for picking the pivot that can save you O(n) storage space. This would need to be included in any production use, especially for large data sets (or in the implementation in the library call you make). In their Algorithms (p.291 of 4th edition), Sedgewick and Wayne show the very concise way to do this in tight loops, as they comment that "A novice Java progammer might even create a new spare array within the recursive method for each partition, which would drastically slow down the sort." This seems a bit harsh on any faithful adherers of Sedgewick's thesis advisor Don Knuth, and Knuth's famous maxim that "premature optimization is the root of all evil", as the tight loops are sharp with edge cases requiring some care (p.292)... and requiring visualizations/experimentation themselves to appreciate and understand. Of course, I like to think that I am in Bret Victor's camp on this, btw.
You can step through the algorithm step-by-step one step at a time, or let it automatically proceed from step to step (with moderate pauses for the animation).
The "Worst Case" option button allows you to see how the algorithm works when the values are chosen for worst-case performance (at least when using the left-most value as the pivot). In this case, the values are already sorted, and the algorithm plods along, requiring O(n2) comparisons.
For the default case (with about 50 values), the animations start dragging a bit as it gets closer and closer to getting the values sorted. Have not yet delved much into what may be going there, although I suspect there are some optimizations possible with the handling of the values for d3 rendering.
And as for the name of this algorithm, I agree with this guy from a few days ago:
Why on earth isn't quicksort called pivot sort? Seriously.
— Nicholas Charriere (@nichochar) January 7, 2014Yeah, I guess the algorithm is "quick", but still, the guy is right.
No comments:
Post a Comment