Visualizing Quicksort

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.

<!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>

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 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>

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js