bmershon/README.md

## README.md

      
    Raw
  

              README.md
            
          
    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.

  
## index.html
<!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);

var line_enter = line.enter().append("line")
    .attr("index", function(d, i) { return "i" + i; })
    .attr("x2", function(d) { return width - 20; })
    .attr("y2", function(d) { return 0; })
    .attr("transform", function(d, i) { return "translate(" + 0 + "," + y(i) + ")"; })
    .attr("class", function(d, i) { return color[d] });

// 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();

var id = setInterval(function step() {
  var action = actions.pop();
  if (action) switch (action.type) {
    case "partition": {
      step();
      line.classed("highlight", function(d, k) {return (action.lt < k && k < action.gt)});
      break;
    }
    case "swap": {
      var t = line[0][action.i];
      line[0][action.i] = line[0][action.j];
      line[0][action.j] = t;
      line.transition().duration(350)
        .attr("transform", function(d, i) { return "translate(" + 0 + "," + y(i) + ")"; });
      break;
    }
  } else {
    line.style("stroke-opacity", 1);
    clearInterval(id);
  }
}, 400);

</script>

## quicksortDijkstra.js
function quicksortDijkstra(arr) {
  var N = arr.length,
      actions = [];

  //recursive sort call with n*log(n) average case complexity
  function sort(a, lo, hi) {
    if(lo >= hi) return;

    var lt = lo,
        i = lo + 1,
        gt = hi,
        v = a[lo]; // partition value

    while(i <= gt) { // elements i through gt are unexamined
      var diff = a[i] - v;
      if (diff < 0) swap(a, lt++, i++);
      else if (diff > 0) swap(a, i, gt--);
      else {
        i++; // equal to key, do keep contiguous stretch going
      }
      actions.push({type: "partition", lo: lo, lt: lt, i: i, gt: gt, hi: hi});
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
  }

  function swap(arr, i, j) {
    var t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    actions.push({type: "swap", i: i, j: j});
  }

  sort(arr, 0, N-1);

  return actions;
}

// Node or browser?
if (typeof window === 'undefined') {
  module.exports = quicksort;

} else {
  window.quicksortDijkstra = quicksortDijkstra;
}

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!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);

	var line_enter = line.enter().append("line")
	.attr("index", function(d, i) { return "i" + i; })
	.attr("x2", function(d) { return width - 20; })
	.attr("y2", function(d) { return 0; })
	.attr("transform", function(d, i) { return "translate(" + 0 + "," + y(i) + ")"; })
	.attr("class", function(d, i) { return color[d] });

	// 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();

	var id = setInterval(function step() {
	var action = actions.pop();
	if (action) switch (action.type) {
	case "partition": {
	step();
	line.classed("highlight", function(d, k) {return (action.lt < k && k < action.gt)});
	break;
	}
	case "swap": {
	var t = line[0][action.i];
	line[0][action.i] = line[0][action.j];
	line[0][action.j] = t;
	line.transition().duration(350)
	.attr("transform", function(d, i) { return "translate(" + 0 + "," + y(i) + ")"; });
	break;
	}
	} else {
	line.style("stroke-opacity", 1);
	clearInterval(id);
	}
	}, 400);

	</script>
	function quicksortDijkstra(arr) {
	var N = arr.length,
	actions = [];

	//recursive sort call with n*log(n) average case complexity
	function sort(a, lo, hi) {
	if(lo >= hi) return;

	var lt = lo,
	i = lo + 1,
	gt = hi,
	v = a[lo]; // partition value

	while(i <= gt) { // elements i through gt are unexamined
	var diff = a[i] - v;
	if (diff < 0) swap(a, lt++, i++);
	else if (diff > 0) swap(a, i, gt--);
	else {
	i++; // equal to key, do keep contiguous stretch going
	}
	actions.push({type: "partition", lo: lo, lt: lt, i: i, gt: gt, hi: hi});
	}
	sort(a, lo, lt - 1);
	sort(a, gt + 1, hi);
	}

	function swap(arr, i, j) {
	var t = arr[i];
	arr[i] = arr[j];
	arr[j] = t;
	actions.push({type: "swap", i: i, j: j});
	}

	sort(arr, 0, N-1);

	return actions;
	}

	// Node or browser?
	if (typeof window === 'undefined') {
	module.exports = quicksort;

	} else {
	window.quicksortDijkstra = quicksortDijkstra;
	}