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