Created
November 28, 2015 08:42
-
-
Save a10k/0862fbbc87d165cc0a7b to your computer and use it in GitHub Desktop.
mergesort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<meta charset="utf-8"> | |
<style> | |
line { | |
stroke: #002776; | |
stroke-width: 5px; | |
} | |
</style> | |
<body> | |
<script src="https://d3js.org/d3.v3.min.js"></script> | |
<script> | |
// Based on http://vis.stanford.edu/protovis/ex/sort.html | |
// Based on work by Robert Sedgewick | |
var w = 800, | |
h = 200; | |
var n = 100, | |
index = d3.range(n), | |
x = d3.scale.ordinal().domain(index).rangePoints([0, w-10]), | |
a = d3.scale.linear().domain([0, n - 1]).range([20, 180]), | |
data = d3.shuffle(d3.range(n)), | |
duration = 250; | |
var svg = d3.select("body").append("svg") | |
.attr("width", w) | |
.attr("height", h); | |
var line = svg.selectAll("line") | |
.data(data) | |
.enter().append("line") | |
.attr("x1", 0) | |
.attr("y1", function(d) { return h-a(d); }) | |
.attr("x2", 0) | |
.attr("y2", h) | |
.attr("transform", transform); | |
start(); | |
// Start the animation! | |
function start() { | |
var passes = mergesort(data).reverse(); | |
update(); | |
function update() { | |
var pass = passes.pop(); | |
line.data(pass, Number) | |
.transition() | |
.duration(duration) | |
.attr("transform", transform); | |
if (passes.length) { | |
setTimeout(update, duration); | |
} else { | |
d3.shuffle(data); | |
setTimeout(start, duration + 4000); | |
} | |
} | |
} | |
function transform(d, i) { | |
return "translate(" + x(i) + ")"; | |
} | |
// Sorts the specified array using bottom-up mergesort, returning an array of | |
// arrays representing the state of the specified array after each insertion for | |
// each parallel pass. The first pass is performed at size = 2. | |
function mergesort(array) { | |
var passes = [], | |
i, | |
j, | |
n = array.length, | |
m = 1; | |
// double the size each pass | |
while (m < array.length) { | |
i = j = 0; while (i < array.length) j += merge(i, i += m, i += m); | |
if (j) passes.push(array.slice()); | |
else m <<= 1; | |
} | |
// Merges two adjacent sorted arrays in-place. | |
function merge(start, middle, end) { | |
middle = Math.min(array.length, middle); | |
end = Math.min(array.length, end); | |
for (; start < middle; start++) { | |
if (array[start] > array[middle]) { | |
var v = array[start]; | |
array[start] = array[middle]; | |
insert(middle, end, v); | |
return true; | |
} | |
} | |
return false; | |
} | |
// Inserts the value v into the subarray specified by start and end. | |
function insert(start, end, v) { | |
while (start + 1 < end && array[start + 1] < v) { | |
var tmp = array[start]; | |
array[start] = array[start + 1]; | |
array[start + 1] = tmp; | |
start++; | |
} | |
array[start] = v; | |
} | |
return passes; | |
} | |
</script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment