public
Last active

Quicksort

  • Download Gist
README.md
Markdown
index.html
HTML
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
<!DOCTYPE html>
<meta charset="utf-8">
<body>
<style>
 
line {
stroke: #000;
stroke-width: 1.5px;
}
 
</style>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
 
var margin = {top: 230, right: 30, bottom: 230, left: 30},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
 
var n = 240,
index = d3.range(n),
data = shuffle(index.slice());
 
var x = d3.scale.ordinal().domain(index).rangePoints([0, width]),
a = d3.scale.linear().domain([0, n - 1]).range([-Math.PI / 4, Math.PI / 4]);
 
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 + height) + ")");
 
var line = svg.selectAll("line")
.data(data)
.enter().append("line")
.attr("index", function(d, i) { return "i" + i; })
.attr("x2", function(d) { return height * Math.sin(a(d)); })
.attr("y2", function(d) { return -height * Math.cos(a(d)); })
.attr("transform", function(d, i) { return "translate(" + x(i) + ")"; });
 
// Fisher–Yates shuffle
function shuffle(array) {
var i = array.length, j, t;
while (--i > 0) {
j = ~~(Math.random() * (i + 1));
t = array[j];
array[j] = array[i];
array[i] = t;
}
return array;
}
 
function quicksort(array) {
var actions = [];
 
function partition(left, right, pivot) {
var v = array[pivot];
swap(pivot, --right);
for (var i = left; i < right; ++i) if (array[i] <= v) swap(i, left++);
swap(left, right);
return left;
}
 
function swap(i, j) {
var t = array[i];
array[i] = array[j];
array[j] = t;
actions.push({type: "swap", i: i, j: j});
}
 
function recurse(left, right) {
if (left < right) {
var pivot = left + ~~(Math.random() * (right - left));
actions.push({type: "partition", pivot: pivot});
pivot = partition(left, right, pivot);
recurse(left, pivot);
recurse(pivot + 1, right);
}
}
 
recurse(0, array.length);
return actions;
}
 
var actions = quicksort(data).reverse();
 
setInterval(function step() {
var action = actions.pop();
if (action) switch (action.type) {
case "partition": {
line.style("stroke", function(d, i) { return i == action.pivot ? "red" : null; });
step();
break;
}
case "swap": {
var t = line[0][action.i];
line[0][action.i] = line[0][action.j];
line[0][action.j] = t;
line.attr("transform", function(d, i) { return "translate(" + x(i) + ")"; });
break;
}
}
}, 20);
 
</script>

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.