Dutch Flag Problem

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 values less than and greater than the pivot element from the left and right ends, respectively, of the subarray to be sorted.

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<style>

svg {
  background-color: #010101;
}

line {
  stroke: #000;
  stroke-width: 10;
  stroke-opacity: 0.6;
}

line.blue {
  stroke: #21468B;
}

line.red {
  stroke: #AE1C28;
}

line.white {
  stroke: #FFF;
}

line.highlight {
  stroke-opacity: 1;
}

</style>
<script src="quicksortDijkstra.js"></script>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

// Modified from Mike Bostock's https://gist.github.com/mbostock/1582075

var margin = {top: 50, right: 150, bottom: 50, left: 150},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom;

var values = [0, 1, 2],
    n = 33,
    index = d3.range(n/3).map(function(d) {return 0})
            .concat(d3.range(n/3).map(function(d) {return 1}))
            .concat(d3.range(n/3).map(function(d) {return 2})),
    data = shuffle(index.slice());

var x = d3.scale.ordinal().domain(d3.range(n)).rangePoints([0, width]),
    y = d3.scale.ordinal().domain(d3.range(n)).rangePoints([0, -height]),
    heightScale = d3.scale.linear().domain([0, n - 1]).range([10, 200]);

var color = ["blue", "white", "red"];

var svg = d3.select("body").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
  .append("g")
    .attr("transform", "translate(" + margin.left + "," + (margin.top + height) + ")");

var line = svg.selectAll("line")
    .data(data);

// Fisher–Yates shuffle
function shuffle(array) {
  var i = array.length, j, t;
  while (--i > 0) {
    j = ~~(Math.random() * (i + 1));
    t = array[j];
    array[j] = array[i];
    array[i] = t;
  }
  return array;
}

var actions = quicksortDijkstra(data).reverse();

</script>

https://d3js.org/d3.v3.min.js