Sorting animation with generators.
Last active
July 7, 2017 01:59
-
-
Save tafsiri/e368022f5c02dde6cde95424aa5b9b28 to your computer and use it in GitHub Desktop.
Sorting animation with generators
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| license: mit | |
| height: 300 | |
| border: no |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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