Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@mjhoy

mjhoy/README.md

Last active December 15, 2015 20:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mjhoy/5318668 to your computer and use it in GitHub Desktop.
Save mjhoy/5318668 to your computer and use it in GitHub Desktop.
Download ZIP
Visualizing Quicksort
Raw
README.md

There are three parts to quicksort. For an array, (1) choose a “pivot” item. Using the pivot, (2) partition the array around the pivot, such that the array to the left of the pivot is less than the pivot; the array to the right of the pivot is greater than the pivot. Finally, (3) invoke quicksort recursively on the left and right partitions.

Recursion can be tricky to understand. Using d3.js, we can represent each recursive call to quicksort as a node, whose parent is the array of which it is a partition, and whose children are its partitions. The base case is when the array is only one element — this is the state of the leaf nodes.

Pivot elements are highlighted red. Sorted arrays have a black circle node; unsorted are light gray. Choosing the pivot is simplified: the first element is picked.

The graph (once sorted) often has an interesting property. If you read top to bottom, left to right, following the pivot elements (those highlighted in red), you will read the final sorted array.

The layout is generated using d3.layout.tree.

Raw
index.html
<!doctype html>
<meta charset='utf-8'>
<style>
#container {
position: relative;
}
#regenerate {
position: absolute;
top: 8px; left: 5px;
border: 1px solid #ccc; background-color: #f9f9f9;
cursor: pointer;
}
#regenerate:hover { background-color: #ccc; }
#arrayVal { position: absolute; top: 10px; left: 70px; border: none; border-bottom: 1px solid #000;}
text { font-family: "Futura", sans-serif; font-size: 11px;}
text.unsorted { fill: #aaa; } text.sorted { fill: #000; }
tspan.pivot { fill: #AC0E0E; font-weight: bold;}
circle.unsorted { fill: #aaa; }
circle.sorted { fill: #000; }
path.link { stroke: #000; fill: none; }
</style>
<div id="container">
<button id="regenerate">Shuffle</button>
<form onSubmit="return getUserValue()">
<input type="text" id="arrayVal" placeholder="1,2,3,etc"/>
<input type="submit" style="display: none;">
</form>
</div>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
var width = 960,
height = 500;
var tree = d3.layout.tree()
.size([920,450]);
var svg = d3.select("#container").append("svg")
.attr("width", width)
.attr("height", height);
var genId = (function () {
var i = 0;
return function () { return i++; };
})();
var slice = [].slice;
var speed = 300;
function choosePivot (node) {
node.pivot = node.arr[0],
node.pivot_index = 0;
}
function tryMerge(node) {
var left = node.left ? undefined : [],
right = node.right ? undefined : [];
if(node.left && node.left.sorted) left = slice.call(node.left.arr);
if(node.right && node.right.sorted) right = slice.call(node.right.arr);
if(left && right) {
node.arr = left.concat([node.pivot]).concat(right);
node.sorted = true;
} else {
node.children.forEach(function(child) { step(child); });
}
}
function partition(node) {
var arr = node.arr,
pivot = node.pivot,
i = 1,
j = 1,
len = arr.length,
temp = undefined;
for(; j < len; j++) {
if(arr[j] < pivot) {
if(j > i) {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
i++;
}
}
if(i > 1) {
arr[0] = arr[i - 1];
arr[i - 1] = pivot;
}
node.pivot_index = i - 1;
}
function createChildNodes(node) {
var arr = node.arr, len = arr.length, i = node.pivot_index;
if(i > 0) {
var first_half = arr.slice(0, i);
var left = qsort_node(first_half);
node.children = [left];
node.left = left;
}
if(i < (len - 1)) {
var second_half = arr.slice(i+1, len);
var right = qsort_node(second_half);
if(!node.children) node.children = [];
node.children.push(right);
node.right = right;
}
}
function step(node) {
var arr = node.arr,
len = arr.length;
if(node.children) {
tryMerge(node);
return;
}
if(len < 2) { // Base case
node.sorted = true;
return;
}
partition(node);
createChildNodes(node);
}
function qsort_node(arr) {
var node = {
"arr" : arr,
"id" : genId()
};
choosePivot(node);
return node;
}
function radius(a) {
return Math.sqrt(a / 2*Math.PI);
}
var update = function (root) {
var nodes = tree.nodes(root),
links = tree.links(nodes);
var node = svg.selectAll(".node")
.data(nodes, function (d) { return d.id; });
node
.transition()
.duration(speed - 50)
.attr("transform", function(d) { return "translate("+d.x + "," + (d.y+25) + ")"; });
var group = node.enter().append("g")
.attr("class", "node")
.attr("transform", function(d) { return "translate("+d.x + "," + (d.y+25) + ")"; });
node.append("circle")
.attr("class", function (d) { return d.sorted ? "sorted" : "unsorted" })
.attr("r", function(d) { return radius(d.arr.length) + 2.0; });
node.select("text").remove();
var text = node.append("text");
text.append("tspan") // Left half
.text(function(d) {
var c = d.arr.slice(0,d.pivot_index);
return c.length ? c+"," : c;
})
text.append("tspan") // Pivot
.text(function(d) { return d.pivot; })
.attr("class", "pivot");
text.append("tspan") // Right half
.text(function(d) {
var c = d.arr.slice(d.pivot_index+1);
return c.length ? "," + c : c;
})
text
.attr("class", function (d) { return d.sorted ? "sorted" : "unsorted" })
.attr("dx", function (d) { return (radius(d.arr.length) * 2.0) + 3.0 + "px"; })
.attr("dy", "0.36em")
.style("font-size", function (d) {
if (d.arr.length > 20) return "7px";
if (d.arr.length > 10) return "10px";
return "12px";
});
var link = svg.selectAll(".link").data(links);
link.transition()
.duration(speed - 50)
.style("stroke-opacity", 1)
.attr("d", d3.svg.diagonal());
link.enter().append("path")
.attr("class", "link")
.attr("transform", function(d) { return "translate(0," + 25 + ")"; })
.attr("d", d3.svg.diagonal())
.style("stroke-opacity", 1e-6);
};
function flush() {
svg.selectAll(".node").remove();
svg.selectAll(".link").remove();
}
function random_array() {
var i, n = 3 + (Math.floor(Math.random() * 25)),
arr = [];
for(i = 0; i < n; i++) {
arr.push(Math.floor(Math.random() * 99));
}
return arr;
}
// Initial.
var root_node = window.root_node = qsort_node(random_array());
update(root_node);
var timer;
function intervalFn () {
step(root_node);
update(root_node);
if(root_node.sorted) {
clearInterval(timer);
setTimeout(function() {
}, 4000);
}
}
timer = setInterval(intervalFn, speed);
d3.select("#regenerate").on("click", function() {
if(timer)clearInterval(timer);
flush();
root_node = qsort_node(random_array());
timer = setInterval(intervalFn, speed);
});
function getUserValue () {
var arr = document.getElementById("arrayVal").value;
arr = arr.split(",").map(function(i) { return parseInt(i, 10); })
flush();
root_node = qsort_node(arr);
timer = setInterval(intervalFn, speed);
return false;
}
</script>
@mjhoy
Copy link
Author

mjhoy commented Apr 5, 2013

see http://bl.ocks.org/mjhoy/5318668

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