// custom variables
var w = 500, h = 190,
num = 30, speed = 50,
algo = "selection", // default algo
dataset, scale, padding = 2, timer,
states = {"default": 0, "finished": 1, "current": 2, "compare": 3, "minimal": 4, "hide": 5},
colors = ["#B7C4CF", "#3565A1", "#D55511", "#74A82A", "#A42F11", "#fff"],
color_default = "#6A6BCD", color_highlight = "#C24787",
svg;
// init the graph
setDataset(num);
setRects(dataset);
// algo definition
var algos = {};
// О(n2)
// http://en.wikipedia.org/wiki/Selection_sort
algos.selection = function() {
var i, j, len = dataset.length, iMin, inI = false;
j = 0; i = len; inI = false;
timer = setInterval(function() {
if (j < len - 1) {
dataset[j].state = states.current;
if (!inI) {
iMin = j;
i = j + 1;
inI = true;
}
if (i < len) {
if (dataset[i - 1].state === states.compare) {
dataset[i - 1].state = states.default;
}
dataset[i].state = states.compare;
if (dataset[i].num < dataset[iMin].num) {
if (iMin !== j)
dataset[iMin].state = states.default;
iMin = i;
dataset[iMin].state = states.minimal;
}
i++;
} else {
inI = false;
if (iMin !== j) {
swap(iMin, j);
}
dataset[i - 1].state = states.default;
dataset[iMin].state = states.default;
dataset[j].state = states.finished;
j++;
}
} else {
dataset[j].state = states.finished;
clearInterval(timer);
}
redrawRects(dataset);
}, speed);
};
// O(n2), Best: O(n)
// http://en.wikipedia.org/wiki/Insertion_sort
algos.insertion = function() {
var i, j, len = dataset.length, inI = false;
j = 1; i = 0; inI = false;
dataset[0].state = states.finished;
timer = setInterval(function() {
if (j < len) {
if (!inI) {
dataset[j].state = states.hide;
i = j - 1;
inI = true;
}
if (i >= 0) {
if (dataset[i].num > dataset[i + 1].num) {
swap(i, i + 1);
} else {
dataset[i + 1].state = states.finished;
j++;
inI = false;
}
i--;
} else {
dataset[0].state = states.finished;
j++;
inI = false;
}
} else {
clearInterval(timer);
}
redrawRects(dataset);
}, speed);
};
// O(n2)
// http://en.wikipedia.org/wiki/Bubble_sort
algos.bubble = function() {
var i, j, len = dataset.length, inI = false, wait;
j = len - 1; i = 0; inI = false; wait = false;
timer = setInterval(function() {
if (j > 0) {
if (!inI) {
i = 0;
inI = true;
}
if (i < j) {
if (!wait) {
if (i != 0) {
dataset[i - 1].state = states.default;
}
dataset[i].state = states.current;
dataset[i + 1].state = states.compare;
} else {
if (dataset[i].num > dataset[i + 1].num) {
swap(i, i + 1);
}
i++;
}
wait = !wait;
} else {
dataset[j - 1].state = states.default;
dataset[j].state = states.finished;
j--;
inI = false;
}
} else {
dataset[0].state = states.finished;
clearInterval(timer);
}
redrawRects(dataset);
}, speed);
};
//algos[algo]();
// common swap function
function swap(i, j) {
var temp = dataset[i];
dataset[i] = dataset[j];
dataset[j] = temp;
}
// generate random dataset
function setDataset(len) {
len = len || 20;
var i = 0;
dataset = [];
for (; i < len; i++) {
dataset[i] = { num: (Math.random() * len * 2) | 0,
state: states.default };
}
scale = d3.scale.linear()
.domain([0, d3.max(dataset, function(d) { return d.num; })])
.range([9, h]);
}
// create rect in svg
function setRects(set) {
document.getElementById("graph").innerHTML = "";
svg = d3.select("#graph")
.append("svg")
.attr("width", w)
.attr("height", h);
var rects = svg.selectAll("rect")
.data(set)
.enter()
.append("rect");
rects.attr("x", function(d, i) {
return i * (w / set.length);
});
rects.attr("y", function(d, i) {
return h - scale(d.num);
});
rects.attr("width", function(d, i) {
return (w / set.length) - padding;
});
rects.attr("height", function(d, i) {
return scale(d.num);
});
rects.attr("fill", function(d, i) {
return colors[d.state];
});
}
// redraw
function redrawRects(set) {
var rects = svg.selectAll("rect")
.data(set)
.transition()
.duration(speed / 2 | 0)
rects.attr("y", function(d, i) {
return h - scale(d.num);
});
rects.attr("width", function(d, i) {
return (w / set.length) - padding;
});
rects.attr("height", function(d, i) {
return scale(d.num);
});
rects.attr("fill", function(d, i) {
return colors[d.state];
});
}
// selection change
document.getElementById("algo").addEventListener("change", function() {
algo = this.value;
});
// reset
document.getElementById("reset").addEventListener("click", function() {
clearInterval(timer);
num = document.getElementById("num").value;
speed = document.getElementById("speed").value;
setDataset(num);
setRects(dataset);
});
// play
document.getElementById("play").addEventListener("click", function() {
clearInterval(timer);
for (var i = dataset.length - 1; i >= 0; i--)
dataset[i].state = states.default;
algos[algo]();
});