This is an interpretation of mbostock's block: Mergesort I.
I kept all the passes through the sort visible to be able to compare the steps of the sorting algorithm.
This is an interpretation of mbostock's block: Mergesort I.
I kept all the passes through the sort visible to be able to compare the steps of the sorting algorithm.
<html> | |
<meta charset="utf-8"> | |
<head> | |
<style> | |
rect { | |
stroke-linecap: round; | |
stroke-width: .25px; | |
stroke: black; | |
fill: #004d00; | |
} | |
</style> | |
<script src="//d3js.org/d3.v3.min.js"></script> | |
</head> | |
<body> | |
<div id="viz" style="width: 100%;height:100%"></div> | |
</body> | |
<script> | |
var n = 64, | |
duration = 1000; | |
var iteration; | |
var margin = 40, | |
vizDims = document.getElementById('viz').getBoundingClientRect(), | |
width = vizDims.width - margin - margin, | |
height = vizDims.height - margin - margin; | |
var x = d3.scale.ordinal() | |
.domain(d3.range(n)) | |
.rangePoints([0, width]); | |
var svg = d3.select("#viz").append("svg") | |
.attr("width", width + margin + margin) | |
.attr("height", height + margin + margin) | |
.append("g") | |
.attr("class", "rows") | |
.attr("transform", "translate(" + margin + "," + margin + ")"); | |
loadRow(); | |
function loadRow() { | |
iteration = 0; | |
var array = d3.shuffle(d3.range(n)), | |
actions = mergesort(array.slice()).reverse(); | |
var rowCount = Math.ceil(actions.length/n), | |
rectHeight = (height/rowCount) * .3, | |
rectWidth = (width/n) * .9; | |
d3.select("svg").select("g").selectAll("*").html('').remove() | |
var rect = svg.append("g") | |
.attr("class", "rect row") | |
.selectAll("rect") | |
.data(array.map(function(v, i) { | |
return { | |
value: v, | |
index: i, | |
id: i, | |
array: 0 | |
}; | |
})) | |
.enter().append("rect") | |
.attr({ | |
"class": "row" + iteration, | |
"id": function(d) {return "rect" + iteration + "_" + d.id}, | |
"x": 0, | |
"y": x(0), | |
"height": rectHeight, | |
"width": rectWidth | |
}) | |
.style("fill-opacity", function(d) { return d.value/n }) | |
.transition().duration(duration) | |
.attr("x", function(d) {return x(d.index)}) | |
var row0 = rect[0]; | |
setTimeout(function() {mergeRows()}, duration * 2); | |
function mergeRows() { | |
var row1 = new Array(n); | |
var transition = d3.transition() | |
.duration(duration/20) | |
.each("start", function start() { | |
var action = actions.pop(); | |
if (action[1] === 0) { iteration++; }; | |
switch (action.type) { | |
case "copy": { | |
var i = action[0], | |
j = action[1], | |
e = row1[j] = row0[i], | |
d = e.__data__; | |
d.index = j; | |
transition.each(function() { | |
var source = d3.select("#rect" + (iteration - 1) + "_" + d.id) | |
d3.select("svg").select(".row").append("rect") | |
.attr({ | |
"class": "row" + iteration, | |
"id": "rect" + iteration + "_" + d.id, | |
"style": source.attr("style"), | |
"x": source.attr("x"), | |
"y": source.attr("y"), | |
"height": rectHeight, | |
"width": rectWidth | |
}) | |
.transition().duration(duration/2) | |
.attr("x", x(d.index)) | |
.attr("y", iteration * rectHeight * 2 ) | |
}); | |
break; | |
} | |
case "swap": { | |
var t = row0; | |
row0 = row1; | |
row1 = t; | |
break; | |
} | |
} | |
if (actions.length) { | |
transition = transition.transition().each("start", start); | |
} else { | |
setTimeout(function() { returnRects()}, duration * 2) | |
}; | |
}); | |
} | |
} | |
function returnRects() { | |
for (z=1; z<=iteration; z++) { | |
var thisRow = d3.selectAll(".row" + z)[0]; | |
for (i=0; i<thisRow.length; i++) { | |
var thisId = d3.select(thisRow[i]).attr("id").split("_")[1]; | |
d3.select(thisRow[i]) | |
.transition().duration(duration * 2) | |
.attr("x", x(thisId)) | |
.attr("y", 0) | |
.remove() | |
} | |
} | |
setTimeout(function() { | |
d3.selectAll('rect') | |
.transition().duration(duration * 2) | |
.attr("x", function() {return x(0)}) | |
setTimeout(function() { loadRow(); }, duration * 2) | |
}, duration * 2) | |
} | |
function mergesort(array) { | |
actions = []; | |
n = array.length; | |
var 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) { | |
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> | |
</html> |