| 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 a slightly different quicksort than this.
This is using Babel so it would work in more browsers, specifically ones that don't support ES2015 generators.
| <!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* recurse (left, right) { | |
| if (left <= right) { | |
| var l = left, r = right, mid = data[Math.floor((left + right) / 2)] | |
| while (l <= r) { | |
| for (; l <= right && data[l] < mid; ++l); | |
| for (; r > left && data[r] > mid; --r); | |
| if (l <= r) { | |
| yield* swap(l++, r--) | |
| } | |
| } | |
| yield * recurse(left, r) | |
| yield * recurse(l, right) | |
| } | |
| } | |
| function* swap (i, j) { | |
| if (i === j) return | |
| yield [i, j] | |
| var t = data[i] | |
| data[i] = data[j] | |
| data[j] = t | |
| } | |
| yield * recurse(0, data.length - 1) | |
| } | |
| 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, i) { return d }) | |
| line.exit().remove() | |
| }) |