Skip to content

Instantly share code, notes, and snippets.

@tafsiri
Created July 7, 2017 02:32
Show Gist options
  • Save tafsiri/b12961508ef0f650ab670374dc0e630c to your computer and use it in GitHub Desktop.
Save tafsiri/b12961508ef0f650ab670374dc0e630c to your computer and use it in GitHub Desktop.
Sorting with generators + history
license: mit
height: 300
border: no

Sorting animation using generators. Maintains history of all previous states.

Made with blockup

<!DOCTYPE html>
<head>
<title>blockup</title>
<style>
body {
font-family: Helvetica, sans-serif;
}
.history {
margin-left:50px;
vertical-align: top;
}
input {
width: 0px;
margin-left:10px;
margin-top:8px;
}
</style>
</head>
<body style='width:720px'>
<p style='text-align: center;'>
<button id='start'>Start</button>
<!-- <button id='shuffle'>Shuffle</button> -->
<p>
<div id=svg-container></div>
<div class='history'>
<label for="history-slider">History</label>
<input id="history-slider" disabled type="range" min="0" max="10" step="1" value="0"/>
</div>
<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 = 120 - margin.top - margin.bottom
const svg = d3.select('#svg-container').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 = 40;
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 states = [];
let sorter;
let historySlider = d3.select('#history-slider');
function start() {
d3.select('#start').attr('disabled', true);
// Render the sorting algorithm as it progresses
sorter = insertionSort(input, compareNumbers);
const interval = 1; // 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")
historySlider.attr('disabled', null);
timer.stop();
} else {
states.push(current.value.slice());
historySlider.attr('max', states.length-1)
historySlider.attr('value', states.length-1)
historySlider.style('width', Math.min(states.length, 500) + "px")
}
}, interval);
}
d3.select('#start')
.on('click', () => {
start();
})
d3.select('#history-slider')
.on('input', function() {
const state = states[this.value];
renderArray(state, 80)
})
// 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