Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active July 30, 2017 21:01
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mbostock/e1e1e7e2c360bec054ba to your computer and use it in GitHub Desktop.
Save mbostock/e1e1e7e2c360bec054ba to your computer and use it in GitHub Desktop.
Quicksort IV
license: gpl-3.0

An improved quicksort animation showing the active partition in black and the active pivot in red.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
.line {
stroke: #000;
stroke-width: 1.5px;
stroke-linecap: round;
}
.line--pivot {
stroke: #f00;
stroke-width: 2.5px;
}
.line--inactive {
stroke: #ddd;
stroke-width: 1px;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var n = 200,
array = d3.shuffle(d3.range(n)),
actions = quicksort(array.slice()).reverse();
var margin = {top: 230, right: 40, bottom: 230, left: 40},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
var x = d3.scale.ordinal()
.domain(d3.range(n))
.rangePoints([0, width]);
var a = d3.scale.linear()
.domain([0, n - 1])
.range([-45, 45]);
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 line = svg.append("g")
.attr("class", "line")
.selectAll("line")
.data(array)
.enter().append("line")
.attr("transform", transform)
.attr("y2", -height);
var transition = d3.transition()
.duration(150)
.each("start", function start() {
var action = actions.pop();
switch (action.type) {
case "swap": {
var i = action[0],
j = action[1],
li = line[0][i],
lj = line[0][j];
line[0][i] = lj;
line[0][j] = li;
transition.each(function() { line.transition().attr("transform", transform); });
break;
}
case "partition": {
line.attr("class", function(d, i) {
return i === action.pivot ? "line--pivot"
: action.left <= i && i < action.right ? null
: "line--inactive";
});
break;
}
}
if (actions.length) transition = transition.transition().each("start", start);
else transition.each("end", function() { line.attr("class", null); });
});
function transform(d, i) {
return "translate(" + x(i) + "," + height + ")rotate(" + a(d) + ")";
}
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) {
if (i === j) return;
var t = array[i];
array[i] = array[j];
array[j] = t;
actions.push({type: "swap", "0": i, "1": j});
}
function recurse(left, right) {
if (left < right - 1) {
var pivot = (left + right) >> 1;
actions.push({type: "partition", "left": left, "pivot": pivot, "right": right});
pivot = partition(left, right, pivot);
recurse(left, pivot);
recurse(pivot + 1, right);
}
}
recurse(0, array.length);
return actions;
}
</script>
@alexjlockwood
Copy link

alexjlockwood commented Jul 30, 2017

Hey Mike,

I was trying to convert this to the d3 v4 API but am having some trouble. Specifically, I'm not sure how to update lines 62-67:

var i = action[0],
    j = action[1],
    li = line[0][i],
    lj = line[0][j];
line[0][i] = lj;
line[0][j] = li;

Do you have any tips?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment