"... a user interface..."

Recently, I have been studying sort algorithms, and thinking about how to create effective interactive visualizations for them. So far, I've done a visualization for Quicksort that kind of shows the power of the divide-and-conquer approach of the algorithm, but does not deal with pivot selection strategy, or deal with the in-place nature of production versions. It seems that a lot of the time, the code for these things is overly concise, static (of course), and stalls deeper appreciation. In the case of Quicksort and pivot selection strategy, this attitude seems supported by this email from (eminent) J Bentley as he was coming up to speed on how a (fairly recent) dual pivot strategy worked; in particular,

I *finally* feel like I understand what is going on. Now that I (think that) I see it, it seems straightforward and obvious. J. Bentley, as quoted in this post on jdk list about new dual pivot approach for Quicksort in 2009

This got me to thinking back on Bret Victor's Thinking the unthinkable, and the importance of notation and interactivity for both learning and exploring new concepts that were previously "unthinkable".

Communicating Technical Information with the Means of the Time
Harder to understand, but it was how they communicated at the time What is the square which when taken with ten of its roots will give a sum of thirty nine? Now the roots in the problem before us are ten. Therefore take five, which multiplied by itself gives twenty five, and amount you add to thirty nine to give sixty four. Having taken the square root of this which is eight, subtract from this half the roots, five leaving three. The number three represents one root of this square, which itself, of course, is nine. Nine therefore gives the square. (al-Khwārizmī, as quoted in Thinking the unthinkable)
  1. For small arrays (length < 17), use the Insertion sort algorithm.
  2. Choose two pivot elements P1 and P2. We can get, for example, the first element a[left] as P1 and the last element a[right] as P2.
  3. P1 must be less than P2, otherwise they are swapped. So, there are the following parts:
    • part I with indices from left+1 to L–1 with elements, which are less than P1,
    • part II with indices from L to K–1 with elements, which are greater or equal to P1 and less or equal to P2,
    • part III with indices from G+1 to right–1 with elements greater than P2,
    • part IV contains the rest of the elements to be examined with indices from K to G.
  4. The next element a[K] from the part IV is compared with two pivots P1 and P2, and placed to the corresponding part I, II, or III.
  5. The pointers L, K, and G are changed in the corresponding directions.
  6. The steps 4 - 5 are repeated while K ≤ G.
  7. The pivot element P1 is swapped with the last element from part I, the pivot element P2 is swapped with the first element from part III.
  8. The steps 1 - 7 are repeated recursively for every part I, part II, and part III
(from Vladimir Yaroslavskiy's Dual-Pivot Quicksort (2009), hailed by J. Bentley as "up there with Hoare's original design and Sedgewick's analysis.")
Better "visualization" for faster comprehension, exploration $$x^2 + 10 x = 39$$
(800 years after al-Khwārizmī)
? ?

I'm still simmering on this. But I think it's appropriate to close with another quote from Bret Victor, and how it might apply for the next wave of understanding and education via interactive online visualizations, made easier and easier to create using the quickly evolving and improving web tools and libraries:

"The birth of modern mathematics is considered to be not any particular mathematical concept, but a user interface. B. Victor

"...a user interface..."

No comments:

Post a Comment

Popular Posts