| license: mit | |
| height: 960 |
Visualization of the quicksort algorithm using d3, showing the array each time it is swapped. The white lines show which values are being swapped.
This is using Babel so it would work in more browsers, specifically ones that don't support ES2015 generators.
I realized after the fact that this was using a slower algorithm than one I've used to make a similar visualization in the past. This example has a faster version of this in-place algorithm.
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| body { | |
| background: black; | |
| } | |
| .line { | |
| fill: white; | |
| opacity: 0.85; | |
| } | |
| </style> | |
| <svg width="960" height="960"></svg> | |
| <script src="//d3js.org/d3.v4.min.js"></script> | |
| <script src="//unpkg.com/babel-standalone@6/babel.min.js"></script> | |
| <script src="//unpkg.com/babel-polyfill@6.16.0/dist/polyfill.js"></script> | |
| <script type="text/babel" src="index.js"></script> |
| var n = 960 | |
| var z = d3.scaleSequential(d3.interpolateRainbow).domain([0, n]) | |
| var data = d3.range(n) | |
| var svg = d3.select('svg') | |
| .attr('width', n) | |
| .attr('height', n) | |
| var g = svg.append('g') | |
| var rect = g.selectAll('rect') | |
| .data(data, Number) | |
| .enter() | |
| .append('rect') | |
| .attr('width', function (d, i) { return i + 1 }) | |
| .attr('height', 1) | |
| .attr('x', 1) | |
| .attr('y', function (d, i) { return i }) | |
| .attr('fill', z) | |
| function* sort () { | |
| function* partition (left, right, pivot) { | |
| var v = data[pivot] | |
| yield * swap(pivot, --right) | |
| for (var i = left; i < right; ++i) if (data[i] <= v) yield * swap(i, left++) | |
| yield * swap(left, right) | |
| return left | |
| } | |
| function* swap (i, j) { | |
| if (i === j) return | |
| yield [i, j] | |
| var t = data[i] | |
| data[i] = data[j] | |
| data[j] = t | |
| } | |
| function* recurse (left, right) { | |
| if (left < right) { | |
| var pivot = Math.floor((left + right) / 2) | |
| pivot = yield * partition(left, right, pivot) | |
| yield * recurse(left, pivot) | |
| yield * recurse(pivot + 1, right) | |
| } | |
| } | |
| yield * recurse(0, data.length) | |
| yield [] | |
| } | |
| var gen = { next () { return { done: true } } } | |
| d3.timer(function () { | |
| var v | |
| while ((v = gen.next()).done) { | |
| d3.shuffle(data) | |
| gen = sort() | |
| } | |
| rect.data(data, Number) | |
| .attr('y', function (d, i) { return i }) | |
| var line = g.selectAll('.line') | |
| .data(v.value) | |
| line.enter().append('rect') | |
| .attr('class', 'line') | |
| .attr('x', 0) | |
| .attr('height', 1) | |
| .attr('width', n) | |
| .merge(line) | |
| .attr('y', function (d) { return d }) | |
| line.exit().remove() | |
| }) |