This animation demonstrates the insertion sort.
Created
August 6, 2014 06:36
-
-
Save chabb/da43926de2f0617f9ab8 to your computer and use it in GitHub Desktop.
Insertion Sort
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"> | |
<title>Quadtree</title> | |
<style> | |
text { | |
font: bold 48px monospace; | |
text-anchor: middle; | |
} | |
</style> | |
<body> | |
<script src="http://d3js.org/d3.v3.min.js"></script> | |
<script> | |
var data = [0,1,2,3,4,5,6,7,8,9]; | |
var margin = {top: 200, right: 100, bottom: 200, left: 100}; | |
var width = 1000-margin.left-margin.right; | |
var height = 900-margin.top-margin.bottom; | |
var rectHeight = 60; | |
var rectWidth = width/data.length; | |
d3.shuffle(data); | |
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 rects = svg.selectAll(".rect") | |
.data(data) | |
.enter() | |
.append("g") | |
.attr("transform", function(d,i){ return "translate("+d*rectWidth+",10)" }) | |
.attr("class","rect"); | |
rects.append("rect") | |
.attr("width",rectWidth) | |
.attr("height",rectHeight) | |
.attr("fill","#245") | |
.attr("opacity",function(d,i) { return i/10}); | |
rects.append("text") | |
.attr("x",rectWidth/2) | |
.attr("y",rectHeight/2+rectHeight/4) | |
.text(function(d,i) {return i+1;}); | |
var min,minIndex; | |
var lastTrans; | |
sort(); | |
/* | |
procédure tri_insertion(tableau T, entier n) | |
pour i de 1 à n-1 | |
x ← T[i] | |
j ← i | |
tant que j > 0 et T[j - 1] > x | |
T[j] ← T[j - 1] | |
j ← j - 1 | |
fin tant que | |
T[j] ← x | |
fin pour | |
fin procédure | |
*/ | |
function sort() { | |
var outer = 0; | |
var inner = 0; | |
for (outer=1;outer<data.length;outer++) { | |
var value = data[outer]; | |
// we take the nth element and make it goes forward the already sorted part | |
for (inner=outer;(inner>0 && data[inner-1]>value) ;inner--) { | |
data[inner] = data[inner-1]; | |
} | |
data[inner] = value; | |
//grab update selection | |
if (outer === 1) { | |
lastTrans = svg.selectAll(".rect").data(data).transition().duration(1200); | |
lastTrans.attr("transform", function(d,i) { | |
return "translate("+ (d*rectWidth) +",10)"; | |
}); | |
} else { | |
lastTrans = lastTrans.transition().attr("transform", function(d,i) { | |
return "translate("+ (data[i]*rectWidth) +",10)"; | |
}); | |
if (outer == data.length-1) { | |
lastTrans.each("end",function(){ | |
d3.shuffle(data); | |
svg.selectAll(".rect").data(data).transition().duration(1200) | |
.attr("transform", function(d,i) { | |
return "translate("+ (d*rectWidth) +",10)"; | |
}).filter(function(d,i){ return i==0}).each("end",function(){sort()}); | |
}) | |
} | |
} | |
} | |
} | |
function restart() { | |
sort(); | |
} | |
function swap(array,indexA,indexB) { | |
if (indexA == indexB) return; | |
var temp = data[indexA]; | |
data[indexA]= data[indexB]; | |
data[indexB] = temp; | |
} | |
</script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment