Exploration of the Quicksort Algorithm

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.

Simple Dynamic App for Exploring the Quicksort Algorithm
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.

Demo video
(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.

Step-by-Step or Auto

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

See Worst Case in Action

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.

Pivot Picking

Old-Timey Lecture (with chalk, even)
on Randomized Algorithm for Quicksort
(UC Davis)
In addition to shuffling the values beforehand, you can also randomly pick the pivot itself so as to (probabilistically) defeat "adversaries" who are trying to force you to make O(n2) comparisons (maybe these are the same guys who are redefining "undefined" on you in javascript). There are interesting avenues here to explore as well.

Other Notes

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:


Yeah, I guess the algorithm is "quick", but still, the guy is right.

No comments:

Post a Comment

Popular Posts