bmershon/README.md

## README.md

      
    Raw
  

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

  
## 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="quicksort.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 = quicksort(data).reverse();

var id = setInterval(function step() {
  var action = actions.pop();
  if (action) switch (action.type) {
    case "partition": {
      step();
      line.classed("highlight", function(d, i) {return (i == action.pivot)});
      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>

## quicksort.js
function quicksort(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 j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
  }

  function partition(a, lo, hi) {
    var i = lo,
        j = hi+1,
        v = a[lo]; // partition value

    while(1) {
      while(a[++i] <= v) if(i == hi) break;
      while(a[--j] >= v) if(j == lo) break;
      if(i >= j) break; // indices cross
      swap(a, i, j);
    }

    swap(a, lo, j); //swap partition element into place
    actions.push({type: "partition", pivot: j});
    return j;
  }

  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.quicksort = quicksort;
}

## 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="quicksort.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 = quicksort(data).reverse();

	var id = setInterval(function step() {
	var action = actions.pop();
	if (action) switch (action.type) {
	case "partition": {
	step();
	line.classed("highlight", function(d, i) {return (i == action.pivot)});
	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 quicksort(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 j = partition(a, lo, hi);
	sort(a, lo, j-1);
	sort(a, j+1, hi);
	}

	function partition(a, lo, hi) {
	var i = lo,
	j = hi+1,
	v = a[lo]; // partition value

	while(1) {
	while(a[++i] <= v) if(i == hi) break;
	while(a[--j] >= v) if(j == lo) break;
	if(i >= j) break; // indices cross
	swap(a, i, j);
	}

	swap(a, lo, j); //swap partition element into place
	actions.push({type: "partition", pivot: j});
	return j;
	}

	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.quicksort = quicksort;
	}