Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
246 lines (195 sloc) 8.91 KB
<html>
<head>
<meta charset="utf-8">
<script src="http://code.jquery.com/jquery-1.7.2.min.js"></script>
<script src="jscex.min.js"></script>
<script src="q.min.js"></script>
<script src="../q-jscex.js"></script>
</head>
<body>
<a href="https://github.com/audreyt/q-jscex"><img style="z-order: 9999;
position: absolute; top: 0; right: 0; border: 0" src="https://s3.amazonaws.com/github/ribbons/forkme_right_darkblue_121621.png" alt="Fork me on GitHub"></a>
<script>
"use strict";
var $async = Q.async.$;
/* Adapted from code by @JeffreyZhao under the 2-clause BSD license:
https://github.com/JeffreyZhao/jscex/blob/master/samples/async/sorting-animations.html
*/
var SortingAnimations = function (canvas) {
var ctx = canvas.getContext ? canvas.getContext("2d") : null;
var lineWidth = 9;
var updateCost = 100;
var compareCost = 100;
var sharedTemp = -1;
var randomArray = function () {
var array = [];
var length = Math.floor(canvas.width / (lineWidth + 1));
for (var i = 1; i <= length; i++) {
array.push(i);
}
array.sort(function() { return (Math.round(Math.random()) - 0.5); });
return array;
}
var paint = function (array, updating, comparing) {
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.lineWidth = lineWidth;
for (var i = 0; i < array.length; i++)
{
var x = (lineWidth + 1) * i + lineWidth / 2;
var height = array[i] * (lineWidth + 1) * canvas.height / canvas.width;
ctx.beginPath();
if (sharedTemp == array[i]) {
if (updating) {
ctx.strokeStyle = "red";
} else if (comparing) {
ctx.strokeStyle = "green";
}
} else if (updating && updating.indexOf(i) >= 0) {
ctx.strokeStyle = "red";
} else if (comparing && comparing.indexOf(i) >= 0) {
ctx.strokeStyle = "green";
} else {
ctx.strokeStyle = "black";
}
ctx.moveTo(x, canvas.height);
ctx.lineTo(x, canvas.height - height);
ctx.stroke();
}
}
var compareAsync = eval($async(function (x, y, comparing) {
paint(array, null, comparing);
$await(Q.delay(compareCost));
return x - y;
}));
var swapAsync = eval($async(function (array, i, j) {
var t = array[i];
array[i] = array[j];
array[j] = t;
paint(array, [i, j]);
$await(Q.delay(updateCost));
}));
var assignAsync = eval($async(function (array, i, value, updating) {
array[i] = value;
paint(array, updating);
$await(Q.delay(updateCost));
}));
var sortOperations = {
Quick: eval($async(function (array) {
var partitionAsync = eval($async(function (begin, end) {
var i = begin;
var j = end;
var pivot = sharedTemp = array[Math.floor((begin + end) / 2)];
while (i <= j) {
while (true) {
var r = $await(compareAsync(array[i], pivot, [i]));
if (r < 0) { i++; } else { break; }
}
while (true) {
var r = $await(compareAsync(array[j], pivot, [j]));
if (r > 0) { j--; } else { break; }
}
if (i <= j) {
$await(swapAsync(array, i, j));
i++;
j--;
}
}
sharedTemp = -1;
return i;
}));
var sortAsync = eval($async(function (begin, end) {
var index = $await(partitionAsync(begin, end));
if (begin < index - 1)
$await(sortAsync(begin, index - 1));
if (index < end)
$await(sortAsync(index, end));
}));
$await(sortAsync(0, array.length - 1));
})),
Bubble: eval($async(function (array) {
for (var i = 0; i < array.length; i++) {
for (var j = 0; j < array.length - i; j++) {
var r = $await(compareAsync(array[j], array[j + 1], [j, j + 1]));
if (r > 0) $await(swapAsync(array, j, j + 1));
}
}
})),
Selection: eval($async(function (array) {
for(var j = 0; j < array.length - 1; j++) {
var mi = j;
for (var i = j + 1; i < array.length; i++) {
var r = $await(compareAsync(array[i], array[mi], [i, mi]));
if (r < 0) { mi = i; }
}
$await(swapAsync(array, mi, j));
}
})),
Shell: eval($async(function (array) {
var gaps = [701, 301, 132, 57, 23, 10, 4, 1];
for (var gap = Math.floor(array.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = gap; i < array.length; i++) {
var temp = sharedTemp = array[i];
var j;
for (j = i; j >= gap; j -= gap) {
var r = $await(compareAsync(temp, array[j - gap], [j - gap]));
if (r < 0) {
$await(assignAsync(array, j, array[j - gap], [j, j - gap]));
} else {
break;
}
}
$await(assignAsync(array, j, temp, [j]));
}
}
sharedTemp = -1;
}))
};
this.supported = !!ctx;
this.randomArray = randomArray;
this.paint = paint;
this.names = [];
for (var m in sortOperations) this.names.push(m);
this.sortAsync = eval($async(function (name, array) {
paint(array);
$await(sortOperations[name](array));
paint(array);
}));
};
</script>
</head>
<body style="margin:5px;">
<p id="controllers">
<select id="comboNames"></select>
<input id="btnSort" type="button" value="Sort" />
</p>
<canvas id="canvas" height="300" width="300">
<span style="font-size:20pt;">Your browser doesn't support canvas.</span>
</canvas>
<script>
var sa = new SortingAnimations($("#canvas")[0]);
var btnSort = $("#btnSort");
if (sa.supported) {
var comboNames = $("#comboNames");
$.each(sa.names, function (_, name) {
comboNames.append($("<option></option>").attr("value", name).text(name));
});
var array = sa.randomArray();
btnSort.click(function () {
btnSort.attr("disabled", "disabled");
comboNames.attr("disabled", "disable");
if (array.sorted) {
array = sa.randomArray();
}
sa.sortAsync(comboNames.val(), array).fin(function () {
array.sorted = true;
btnSort.removeAttr("disabled");
comboNames.removeAttr("disabled");
});
});
sa.paint(array);
} else {
$("#controllers").css("display", "none");
}
</script>
</body>
</html>