An improved animation of mergesort. As the name suggests, the algorithm merges sorted arrays, starting with arrays of length 1 and doubling at each step. The two subarrays currently being merged are shown in black.
forked from mbostock‘s block: Mergesort II
forked from anonymous‘s block: Mergesort II: commented
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.line {
stroke: #000;
stroke-width: 1.5px;
stroke-linecap: round;
}
.line--inactive {
stroke: #ddd;
stroke-width: 1px;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
// 1: data is array of numbers from 0 to 199, randomly ordered
var n = 200,
array = d3.shuffle(d3.range(n)),
actions = mergesort(array.slice()).reverse();
var margin = {top: 180, right: 40, bottom: 180, left: 40},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
// y translates ...
var y = d3.scale.ordinal()
.domain([1, 0])
.rangeRoundBands([height, 0], .3);
var x = d3.scale.ordinal()
.domain(d3.range(n))
.rangePoints([0, width]);
var a = d3.scale.linear()
.domain([0, n - 1])
.range([-45, 45]);
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 + ")");
var line = svg.append("g")
.attr("class", "line")
.selectAll("line")
.data(array.map(function(v, i) {
return {
// 2. v is the value
value: v,
// index is the position
index: i,
// set array to 0, will alternate between 0 and 1
array: 0
};
}))
// 3: each datapoint is represented with a line
.enter().append("line")
// 4: each line has a transformation applied and is given a "y2" value
// y1, x1, and x2 are set implicitely to 0
// what is the transformation?
.attr("transform", transform)
.attr("y2", -y.rangeBand());
var line0 = line[0],
line1 = new Array(n);
var transition = d3.transition()
.duration(75)
.each("start", function start() {
var action = actions.pop();
switch (action.type) {
case "merge": {
d3.selectAll(line0).attr("class", function(d, i) { return action.left <= i && i < action.end ? null : "line--inactive"; });
break;
}
case "copy": {
var i = action[0],
j = action[1],
e = line1[j] = line0[i],
d = e.__data__;
d.index = j;
d.array = (d.array + 1) & 1;
transition.each(function() { d3.select(e).transition().attr("transform", transform); });
break;
}
case "swap": {
var t = line0;
line0 = line1;
line1 = t;
break;
}
}
if (actions.length) transition = transition.transition().each("start", start);
});
// 5: transformation is a translation horiztonally, vertically, and a rotation
function transform(d) {
// what is the x, y, and a functions?
return "translate(" + x(d.index) + "," + y(d.array) + ")rotate(" + a(d.value) + ")";
}
function mergesort(array) {
var actions = [],
n = array.length,
array0 = array,
array1 = new Array(n);
for (var m = 1; m < n; m <<= 1) {
for (var i = 0; i < n; i += (m << 1)) {
merge(i, Math.min(i + m, n), Math.min(i + (m << 1), n));
}
actions.push({type: "swap"});
array = array0, array0 = array1, array1 = array;
}
function merge(left, right, end) {
actions.push({type: "merge", left: left, end: end});
for (var i0 = left, i1 = right, j = left; j < end; ++j) {
if (i0 < right && (i1 >= end || array0[i0] <= array0[i1])) {
array1[j] = array0[i0];
actions.push({type: "copy", "0": i0++, "1": j});
} else {
array1[j] = array0[i1];
actions.push({type: "copy", "0": i1++, "1": j});
}
}
}
return actions;
}
</script>