Some Visualizations to Help Understand Quicksort

In the last few weeks, I've put together a few visualizations related to Quicksort, and this post collects the links into one place (mainly for me).

Visualization of Yaroslavskiy's Dual Pivot Partitioning for Quicksort

I have recently been playing with various aspects of the quicksort algorithm. One aspect that is fascinating to me is that just a few years ago (in 2009), there were significant improvements made to it by Vladimir Yaroslavskiy. He showed that a dual-pivot approach could be better performing than existing methods, despite the general consensus which had been (justifiably) likely swayed by Robert's Sedgewick's analyses several decades ago. Yaroslavskiy's algorithm was tweaked by Jon Bentley and Joshua Bloch and included as the core sorting algorithm in Java 7. This is no minor accomplishment, imo.

I am very curious why Yaroslavskiy decided to tackle the problem this way, given the historical opinion of dual pivot methods.

Anyway, I built on some of my recent little projects to create a visualization that is intended to provide some insight into Yaroslavskiy's approach.

The visualization is available here (best on Chrome desktop at the moment, I haven't used it on any physical mobile tablets yet, I just took a peek or two in the ChromeDev emulator for iPad and Nexus 7):

Click Here for Site for Yaroslavskiy Dual Pivot Quicksort Partitioning Visualization

(site url is https://googledrive.com/host/0B2GQktu-wcTiNEtsejVjRWlmaWs/)

The "Music" of the Quicksort Partitioning Step - an Initial Experiment

I have been experimenting with different ways to appreciate the simple but ubiquitous Quicksort algorithm. My first project dealt with visualizing how the "divide-and-conquer" process works, as described here. The one here delves a little into the partitioning process of the algorithm, in an experiment by which the web audio api is used to sound notes/chords at certain times in the partitioning process. It is a work-in-progress, and apparently sounds different on different browsers. Chrome on the desktop works OK, but Chrome on my Nexus 7 plays the C chord with an odd buzz, as does Safari on the desktop.

It is embedded below from this site on googledrive.

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.