Brooks Mershon bmershon

Compare this naive implementation of quicksort to Dijkstra's implementation of 3-way partitioning.

The Dutch national flag problem exposes an example of an input for which quicksort performs poorly. When there are many duplicates in the array to be sorted, it will often be the case that unecessary function calls to the recursive sort() method will be made on subarrays that already contain elements that are all equal.

The three bars of the Dutch National Flag hint towards another way of thinking about partitioning an unsorted array: move elements around such that elements we have all the elements less than pivot element, followed by all elements equal to the pivot element, and then all elements greater than the pivot element. In the case of an unsorted array of just three different values, say, red, white, and blue, we can imagine that sorting these shuffled values around would lead to a final structure much like the Dutch National Flag.

This implementation of quicksort uses Dijkstra's clever partitioning algorithm to expand regions of v

An improvement upon a previous presentation of Shellsort. Here, each color indicates the elements which may be swapped during a given iteration of Shellsort.

The number of colors converges to 1 by following a sequence generated by the following code:

  while (h < N/3) h = 3*h + 1;

  ...
  
 //in the main loop

An implementation of shellsort with a visualization based off of Mike Bostock's Quicksort animation.

Red lines indicate every hth index as the algorithm performs insertion sort for h independent interleaved sorted subsequences.

This was developed at the Washington Post as a prototype for an illustration about the devastating effects of U.S. nuclear testing carried out around the Marshall Islands. The purpose of this prototype was to demonstrate a means for showing geographic information what would otherise require many "small multiples" in a more dense, interactive, and perhaps intuitive way.

The use of context-senstive label placement that attempts to avoid cluttering the view with unecessary details was one of the most valuable design exercises involved in creating this graphic prototype.

SVG rendering is not performant enough for smooth mouse interaction of the 3D globe. The author's 2011 Mac Book Air, for example, manages a mere 11 frames per second as it performs the main update loop. Performance could be improved with more thoughtful managment of D3 4.0 selections as well as canvas rendering using the new D3 4.0 semantics for drawing paths.

N.B. Hex binning was performed using longitude and latitude: this produces a distor

A convex combination of three vectors in the plane allows us to represent any vector in the convex hull determined by those three vectors.

I wanted to make a looping animation after checking out the sweet work of Florian de Looij (@FloriandeLooij).

	height: 768
	width: 1050
	border: no
	license: gpl-3.0