|
<!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> |
