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):
(site url is https://googledrive.com/host/0B2GQktu-wcTiNEtsejVjRWlmaWs/)
I haven't tweaked the css enough to be sure if it will work in an iframe here (or some mobile environments), but here are a few screenshots:
The Visualization is Synchronized with the Displayed Source of the Algorithm
While visualizing the partitioning process is nice, it was important to me to tie each visual step to a specific place in the source code algorithm itself (e.g., to see two aspects of the "crossing pointers" technique). For this reason, I include pseudocode as listed in Sebastian Wild and Markus Nebel's 2013 analysis of the algorithm. For each step in the partitioning process, the corresponding line in the source code is highlighted, as well as explanatory annotations on the visualization itself. Synchronizing these connections was a lot more work than I anticipated - the conciseness of the algorithm is deceptive.
Using Donald Knuth's Beautiful "Computer Modern" Font
Since I was using the pseudocode as listed in wild and Nebel's paper, I wanted to capture the feel by using a font as close as possible. They are using TeX (I assume), which renders gorgeous mathematics equations. I knew that I could hook up MathJax to do this, but I was concerned about some of the lags I've seen in rendering MathJax equations for the purpose of this project. I then looked it up and found out that the TeX font is Donald Knuth's "Computer Modern" font, and that Christian Perfect had created the ttf files for it (described in his blog post Using Computer Modern on the web). And so using @font-face, this font was usable as a web font. And it turns out that you can use this font in svg text elements, which helps to visually tie the graphic area with the source code.
What the ℓ?
One of the things that stood out to me in the algorithm source was the little script "el". I wanted to make sure and include it, but since I wasn't using TeX I couldn't get it using "\ell". However, I learned that this is just unicode character 2113. You can escape it in html, or even use it directly in javascript code just like any other character (which I did, which is weird to look at in the code).
More to Do
There's 'more to do here. Very much a work-in-progress.
The animations need to be sped up when in "auto" modeDone - it goes fast but watchable (imo) when in automode- I need to make some more passes through the annotation text
- I want to find some more canned examples for highlighting various aspects of the algorithm's performance
- Make sure it works ok on tablets There's likely some glitches to root out in this beta project, and I want to make sure it ends up working ok on tablets (please feel free to let me know if it works for you).
No comments:
Post a Comment