Skip to content

Instantly share code, notes, and snippets.

@tafsiri
Last active July 7, 2017 01:59
Show Gist options
  • Save tafsiri/e368022f5c02dde6cde95424aa5b9b28 to your computer and use it in GitHub Desktop.
Save tafsiri/e368022f5c02dde6cde95424aa5b9b28 to your computer and use it in GitHub Desktop.
Sorting animation with generators
license: mit
height: 300
border: no
<!DOCTYPE html>
<title>blockup</title>
<body style='width:720px'>
<p style='text-align: center;'>
<button id='start'>Start</button>
<button id='shuffle'>Shuffle</button>
<p>
<script src='https://d3js.org/d3.v4.min.js'></script>
<script src='script.js'></script>
</body>
// Some initial setup
const margin = { top: 5, right: 50, bottom: 5, left: 50 }
const width = 720 - margin.left - margin.right
const height = 150 - margin.top - margin.bottom
const svg = d3.select('body').append('svg')
.attr('width', width + margin.left + margin.right)
.attr('height', height + margin.top + margin.bottom)
const g = svg.append('g')
.attr('transform', `translate(${margin.left}, ${margin.top})`)
// Set up our input data.
const NUM_VALS = 50;
let input = [];
for (let i = 0; i < NUM_VALS; i++) {
input[i] = i;
}
const x = d3.scaleBand()
.domain(input.map((d, i) => i))
.range([0, width])
.padding([.2]);
const minBarHeight = 10;
const maxBarHeight = 100;
const barHeight = d3.scaleLinear()
.domain(d3.extent(input))
.range([minBarHeight, maxBarHeight]);
// Render the randomized array.
shuffle(input)
renderArray(input);
// Adapted from https://en.wikipedia.org/wiki/Insertion_sort#Algorithm_for_insertion_sort
function* insertionSort(arr, comparator) {
for (let i = 1; i < arr.length; i++) {
let j = i;
while (j > 0 && arr[j-1] > arr[j]) {
let temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j = j - 1;
yield arr;
}
}
return arr;
}
/**
* Render array of numbers using bar height for magnitude
*/
function renderArray(array, duration=100) {
let rects = g.selectAll("rect")
.data(array, d => d);
const rEnter = rects.enter()
.append('rect')
.attr('x', (d, i) => x(i))
.attr('y', (d) => maxBarHeight - barHeight(d) )
.attr('width', x.bandwidth())
.attr('height', d => barHeight(d));
rects.merge(rEnter)
.transition()
.duration(duration)
.attr('x', (d, i) => x(i))
.attr('fill', 'grey');
rects.exit().remove();
}
// Fisher-yates shuffle via https://bost.ocks.org/mike/shuffle/compare.html
function shuffle(array) {
var m = array.length, t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
}
function compareNumbers(a, b) {
return a - b;
}
let sorter;
function start() {
d3.select('#start').attr('disabled', true);
d3.select('#shuffle').attr('disabled', true);
// Render the sorting algorithm as it progresses
sorter = insertionSort(input, compareNumbers);
const interval = 30; // how quickly should the process go
const timer = d3.interval(function(elapsed) {
const current = sorter.next();
renderArray(current.value, interval);
if (current.done) {
console.log("Generator done")
d3.select('#start').attr('disabled', null);
d3.select('#shuffle').attr('disabled', null);
timer.stop();
}
}, interval);
}
d3.select('#start')
.on('click', () => {
start();
})
d3.select('#shuffle')
.on('click', () => {
shuffle(input)
renderArray(input);
})
// Run an iterator to completion
function complete(iterator) {
let it = iterator.next();
while (!it.done) {
it = iterator.next()
}
return it.value;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment